Алгоритм определения, содержит ли массив n ... n + m?

Question

Я видел этот вопрос на Reddit, и не было представлено никаких положительных решений, и я подумал, что это будет идеальный вопрос, чтобы задать его здесь. Это было в ветке о вопросах интервью:

Напишите метод, который принимает массив типа int размера m и возвращает (True / False), если массив состоит из чисел n ... n + m-1, всех чисел в этом диапазоне и только чисел в этом диапазоне , Массив не гарантируется для сортировки. (Например, {2,3,4} вернет true. {1,3,1} вернет false, {1,2,4} вернет false.

Проблема, с которой я столкнулся, заключается в том, что мой интервьюер постоянно просил меня оптимизировать (быстрее O (n), меньше памяти и т. Д.) До такой степени, что он утверждал, что вы можете сделать это за один проход массива, используя постоянный объем памяти. Никогда этого не понимал.

Вместе с вашими решениями укажите, если они предполагают, что массив содержит уникальные элементы. Также укажите, если ваше решение предполагает, что последовательность начинается с 1. (Я немного изменил вопрос, чтобы разрешить случаи, когда он идет 2, 3, 4 ...)

edit: Сейчас я считаю, что не существует линейного во времени и постоянного в пространстве алгоритма, который обрабатывает дубликаты. Кто-нибудь может это проверить?

Проблема дубликатов сводится к тестированию, чтобы увидеть, содержит ли массив дубликаты за O (n) время, O (1) пространство. Если это можно сделать, вы можете сначала протестировать и, если нет дубликатов, запустить опубликованные алгоритмы. Итак, можете ли вы проверить наличие дубликатов в O (n) времени O (1) пространстве?

Answer 1

Учитывая это -

Напишите метод, который принимает массив int размером m ...

Полагаю, справедливо будет заключить, что существует верхний предел для m, равный величине наибольшего int (типично 2 ^ 32). Другими словами, даже если m не задано как int, тот факт, что массив не может иметь дубликаты, подразумевает, что не может быть больше, чем число значений, которые вы можете сформировать из 32 битов, что, в свою очередь, подразумевает, что m ограничено, чтобы быть также int.

Если такой вывод приемлем, тогда я предлагаю использовать фиксированное пространство (2 ^ 33 + 2) * 4 байта = 34 359 738 376 байтов = 34,4 ГБ для обработки всех возможных случаев. (Не считая места, требуемого входным массивом и его циклом).

Конечно, для оптимизации я бы сначала учел m и выделил только фактическую необходимую сумму (2m + 2) * 4 байта.

Если это приемлемо для ограничения пространства O (1) - для поставленной задачи - тогда позвольте мне перейти к алгоритмическому предложению ...:)

Допущения : массив из m целых, положительных или отрицательных, ни один из которых не превышает 4 байта. Дубликаты обрабатываются. Первое значение может быть любым допустимым int. Ограничьте м, как указано выше.

Сначала , создайте массив int длиной 2m-1, ary и предоставьте три переменные int: left , diff и вправо . Обратите внимание, что составляет 2 м + 2 ...

Second , возьмите первое значение из входного массива и скопируйте его в позицию m-1 в новом массиве. Инициализируйте три переменные.

• набор все [м-1] - nthVal // n = 0
• set left = diff = right = 0

Третий , переберите оставшиеся значения во входном массиве и сделайте следующее для каждой итерации:

• set diff = nthVal - ary [m-1]
• if ( diff > m-1 + right || diff <1-m + <strong>left ) return false // вне границ
• if ( ary [m-1 + diff ]! = Null) вернуть false // duplicate
• set ary [m-1 + diff ] = nthVal
• if ( diff > left ) left = diff // ограничивает левую границу дальше вправо
• if ( diff <<strong> right ) right = diff // ограничивает правую границу дальше влево

Я решил поместить это в код, и это сработало.

Вот рабочий пример с использованием C #:

public class Program
{
    static bool puzzle(int[] inAry)
    {
        var m = inAry.Count();
        var outAry = new int?[2 * m - 1];
        int diff = 0;
        int left = 0;
        int right = 0;
        outAry[m - 1] = inAry[0];
        for (var i = 1; i < m; i += 1)
        {
            diff = inAry[i] - inAry[0];
            if (diff > m - 1 + right || diff < 1 - m + left) return false;
            if (outAry[m - 1 + diff] != null) return false;
            outAry[m - 1 + diff] = inAry[i];
            if (diff > left) left = diff;
            if (diff < right) right = diff;
        }
        return true;
    }

    static void Main(string[] args)
    {
        var inAry = new int[3]{ 2, 3, 4 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[3] { 21, 31, 41 };
        Console.WriteLine(puzzle(inAry));
        Console.ReadLine();
    }

}

Answer 2

Я не думаю, что хорошо объяснил себя в своем первоначальном посте (ниже сплошной линии). Например, для ввода [1 2 3 4 5] алгоритм вычисляет сумму:

-1 + 2 - 3 + 4 - 5 

, который должен быть равен

-1^5 * ceil(5/2)

Псевдокод ниже показывает, как проверяются векторы, которые не начинаются с 1. Алгоритм обрабатывает случаи, когда входной вектор не отсортирован и / или содержит дубликаты.

---

Следующий алгоритм решает задачу путем вычисления знакопеременных сумм векторных элементов:

-1 + 2 - 3 + 4 - 5 + .... + m = (-1)^m * ceil(m/2)

, где ceil округляется до ближайшего целого числа. Другими словами, нечетные числа вычитаются из промежуточного итога, и к нему добавляются четные числа.

function test(data, m)
    altSum = 0
    n = Inf
    mCheck = -Inf
    for ii = 1:m
    {
        if data(ii) < n
            n = data(ii)
        if data(ii) > mCheck
            mCheck = data(ii)
        altSum = altSum + (-1)^data(ii) * data(ii)
    }
    if ((mCheck-n+1!=m) || (-1)^(n+m-1) * ceil((n+m-1)/2) - ((-1)^(n-1) * ceil((n-1)/2)) != altSum
        return false
    else
        return true

Answer 3

Если вы хотите узнать сумму чисел [n ... n + m - 1], просто используйте это уравнение.

var sum = m * (m + 2 * n - 1) / 2;

Это работает для любого числа, положительного или отрицательного, даже если n - десятичное число.

Answer 4

Почему другие решения используют суммирование каждого значения? Я думаю, что это рискованно, потому что, когда вы складываете O (n) элементов в одно число, технически вы используете больше, чем O (1) пробела.

O (1) указывает на постоянное пространство, которое не изменяется на число n. Неважно, если это 1 или 2 переменные, если это постоянное число. Почему вы говорите, что это больше, чем O (1) пробел? Если вы вычисляете сумму из n чисел, накапливая ее во временной переменной, вы все равно будете использовать ровно 1 переменную.

Комментирование в ответе, поскольку система еще не позволяет мне писать комментарии.

Обновление (в ответ на комментарии): в этом ответе я имел в виду O (1) пробел, где пропущено «пробел» или «время». Цитируемый текст является частью более раннего ответа, на который это ответ.

Answer 5

Ответ от "nickf" не работает, если массив не отсортирован var_dump (testArray (array (5, 3, 1, 2, 4), 1, 5)); // выдает "дубликаты" !!!!

Также ваша формула для вычисления суммы ([n ... n + m-1]) выглядит неверно .... правильная формула (m (m + 1) / 2 - n (n-1) / 2)

Answer 6

Oops! Я попал в повторяющийся вопрос и не увидел здесь уже идентичных решений. И я подумал, что наконец-то сделал что-то оригинальное! Вот исторический архив, когда я был немного более доволен:

---

Ну, я не уверен, удовлетворяет ли этот алгоритм всем условиям. На самом деле, я даже не подтвердил, что это работает за пределами пары тестовых случаев, которые я пробовал Даже если у моего алгоритма есть проблемы, я надеюсь, что мой подход найдет некоторые решения.

Этот алгоритм, насколько мне известно, работает в постоянной памяти и сканирует массив три раза. Возможно, дополнительным бонусом является то, что он работает для всего диапазона целых чисел, если это не было частью исходной задачи.

Я не большой человек с псевдокодом, и я действительно думаю, что код может иметь больше смысла, чем слова. Вот реализация, которую я написал на PHP. Обратите внимание на комментарии.

function is_permutation($ints) {

  /* Gather some meta-data. These scans can
     be done simultaneously */
  $lowest = min($ints);
  $length = count($ints);

  $max_index = $length - 1;

  $sort_run_count = 0;

  /* I do not have any proof that running this sort twice
     will always completely sort the array (of course only
     intentionally happening if the array is a permutation) */

  while ($sort_run_count < 2) {

    for ($i = 0; $i < $length; ++$i) {

      $dest_index = $ints[$i] - $lowest;

      if ($i == $dest_index) {
        continue;
      }

      if ($dest_index > $max_index) {
        return false;
      }

      if ($ints[$i] == $ints[$dest_index]) {
        return false;
      }

      $temp = $ints[$dest_index];
      $ints[$dest_index] = $ints[$i];
      $ints[$i] = $temp;

    }

    ++$sort_run_count;

  }

  return true;

}

Answer 7

Массив содержит N чисел, и вы хотите определить, являются ли два из числа суммируют с заданным числом K. Например, если входное значение равно 8,4, 1,6 и K равно 10, ответ да (4 и 6). Число может быть использовано дважды. Сделайте следующее. а. Дайте алгоритм O (N2) для решения этой проблемы. б. Дайте алгоритм O (N log N) для решения этой проблемы. (Подсказка: сначала отсортируйте элементы. После этого вы сможете решить проблему за линейное время.) с. Код обоих решений и сравнить время выполнения ваших алгоритмов. 4.

Answer 8

примечание : этот комментарий основан на исходном тексте вопроса (с тех пор он был исправлен)

Если вопрос поставлен точно , как написано выше (и это не просто опечатка), и для массива размера n функция должна вернуть (True / False), если массив состоит из чисел ... n + 1,

... тогда ответ всегда будет ложным, потому что массив со всеми числами 1 ... n + 1 будет иметь размер n + 1, а не n. следовательно, на вопрос можно ответить в O (1). :)

Answer 9

Я предлагаю следующее:

Выберите конечный набор простых чисел P_1, P_2, ..., P_K и вычислите вхождения элементов во входной последовательности (минус минимум) по модулю каждого P_i. Шаблон действительной последовательности известен.

Например, для последовательности из 17 элементов, по модулю 2 мы должны иметь профиль: [9 8], по модулю 3: [6 6 5], по модулю 5: [4 4 3 3 3] и т. Д.

Комбинируя тест с использованием нескольких баз, мы получаем все более и более точный вероятностный тест. Поскольку записи ограничены целочисленным размером, существует конечная база, обеспечивающая точный тест. Это похоже на вероятностные тесты псевдопримальности.

S_i is an int array of size P_i, initially filled with 0, i=1..K
M is the length of the input sequence
Mn = INT_MAX
Mx = INT_MIN

for x in the input sequence:
  for i in 1..K: S_i[x % P_i]++  // count occurrences mod Pi
  Mn = min(Mn,x)  // update min
  Mx = max(Mx,x)  // and max

if Mx-Mn != M-1: return False  // Check bounds

for i in 1..K:
  // Check profile mod P_i
  Q = M / P_i
  R = M % P_i
  Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1
  if this test fails, return False

return True

Answer 10

def test(a, n, m):
    seen = [False] * m
    for x in a:
        if x < n or x >= n+m:
            return False
        if seen[x-n]:
            return False
        seen[x-n] = True
    return False not in seen

print test([2, 3, 1], 1, 3)
print test([1, 3, 1], 1, 3)
print test([1, 2, 4], 1, 3)

Обратите внимание, что это только делает один проход через первый массив, не учитывая линейный поиск, включенный в not in. :)

Я также мог бы использовать питон set, но я выбрал простое решение, в котором характеристики производительности set не должны рассматриваться.

Обновление: Smashery указал, что я неправильно проанализировал «постоянный объем памяти», и это решение фактически не решает проблему.