Алгоритм определения, содержит ли массив 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

Мне нравится идея Грега Хьюгилла о сортировке по Radix. Чтобы найти дубликаты, вы можете отсортировать за O (N) время, учитывая ограничения на значения в этом массиве.

В течение O (1) промежутка времени O (N), который восстанавливает первоначальное упорядочение списка, вам не нужно выполнять фактическую замену этого числа; Вы можете просто пометить его флагом:

//Java: assumes all numbers in arr > 1
boolean checkArrayConsecutiveRange(int[] arr) {

// find min/max
int min = arr[0]; int max = arr[0]
for (int i=1; i<arr.length; i++) {
    min = (arr[i] < min ? arr[i] : min);
    max = (arr[i] > max ? arr[i] : max);
}
if (max-min != arr.length) return false;

// flag and check
boolean ret = true;
for (int i=0; i<arr.length; i++) {
    int targetI = Math.abs(arr[i])-min;
    if (arr[targetI] < 0) {
        ret = false; 
        break;
    }
    arr[targetI] = -arr[targetI];
}
for (int i=0; i<arr.length; i++) {
    arr[i] = Math.abs(arr[i]);
}

return ret;
}

Хранение флагов внутри данного массива - это обман, и он не очень хорошо работает с распараллеливанием. Я все еще пытаюсь придумать способ сделать это, не касаясь массива в O (N) времени и O (log N) пространстве. Проверка по сумме и по сумме наименьших квадратов (arr [i] - arr.length / 2.0) ^ 2 кажется, что это может сработать. Единственная определяющая характеристика, которую мы знаем о массиве 0 ... m без дубликатов, это то, что он распределен равномерно; мы просто должны это проверить.

Теперь, если бы я только мог это доказать.

Я хотел бы отметить, что решение выше с участием факториала занимает O (N) место для хранения самого факториала. N! > 2 ^ N, для хранения которого требуется N байт.

Answer 2

Если это была опечатка и вопрос о том, что все числа находятся в диапазоне 1 ... n, то:

def try_arr(arr):
    n = len(arr)
    return (not any(x<1 or x>n for x in arr)) and sum(arr)==n*(n+1)/2

$ print try_arr([1,2,3])
True

$ print try_arr([1,3,1])
False

$ print try_arr([1,2,4])
False

Примечания:

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

• Если размер массива (n) был известен, вы можете изменить его для потоковой передачи данных, например, из входного файла, и практически не использовать память (1 временная переменная внутри sum () и 1 переменная для текущего пункт взят из потока)

• any () является новым в python 2.5 (но у вас есть альтернативные способы выразить то же самое в более ранних версиях python)

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

Answer 3

Таким образом, существует алгоритм, который принимает O (n ^ 2), который не требует модификации входного массива и занимает постоянное пространство.

Сначала предположим, что вы знаете n и m. Это линейная операция, поэтому она не добавляет дополнительной сложности. Далее предположим, что существует один элемент, равный n, и один элемент, равный n+m-1, а все остальные находятся в [n, n+m). Учитывая это, мы можем свести проблему к наличию массива с элементами в [0, m).

Теперь, поскольку мы знаем, что элементы ограничены размером массива, мы можем рассматривать каждый элемент как узел с одной ссылкой на другой элемент; другими словами, массив описывает ориентированный граф. В этом ориентированном графе, если нет повторяющихся элементов, каждый узел принадлежит циклу, то есть узел доступен из себя за m или менее шагов. Если есть дублирующий элемент, то существует один узел, который вообще недоступен сам по себе.

Итак, чтобы обнаружить это, вы проходите весь массив от начала до конца и определяете, возвращается ли каждый элемент к себе в <=m шагах. Если какой-либо элемент недоступен в <=m шагах, то у вас есть дубликат и вы можете вернуть false. В противном случае, когда вы закончите посещение всех элементов, вы можете вернуть true:

for (int start_index= 0; start_index<m; ++start_index)
{
    int steps= 1;
    int current_element_index= arr[start_index];
    while (steps<m+1 && current_element_index!=start_index)
    {
        current_element_index= arr[current_element_index];
        ++steps;
    }

    if (steps>m)
    {
        return false;
    }
}

return true;

Вы можете оптимизировать это, сохраняя дополнительную информацию:

1. Запишите сумму длины цикла от каждого элемента, если цикл не посещает элемент перед этим элементом, назовите его sum_of_steps.
2. Для каждого элемента только шаг m-sum_of_steps узлов. Если вы не возвращаетесь к начальному элементу и не посещаете элемент перед начальным элементом, вы нашли цикл, содержащий дубликаты элементов, и можете вернуть false.

Это все еще O (n ^ 2), например {1, 2, 3, 0, 5, 6, 7, 4}, но это немного быстрее.

Answer 4

МОЙ ТЕКУЩИЙ ЛУЧШИЙ ВАРИАНТ

def uniqueSet( array )
  check_index = 0; 
  check_value = 0; 
  min = array[0];
  array.each_with_index{ |value,index|
         check_index = check_index ^ ( 1 << index );
         check_value = check_value ^ ( 1 << value );
         min = value if value < min
  } 
  check_index =  check_index  << min;
  return check_index == check_value; 
end

O (n) и пробел O (1)

Я написал сценарий для комбинаций грубой силы, которые могли потерпеть неудачу, но он не нашел ни одной. Если у вас есть массив, который противоречит этой функции, сообщите об этом. :)

---

@J.F. Себастьян

Это не настоящий алгоритм хеширования. Технически, это высокоэффективный упакованный логический массив «видимых» значений.

ci = 0, cv = 0
[5,4,3]{ 
  i = 0 
  v = 5 
  1 << 0 == 000001
  1 << 5 == 100000
  0 ^ 000001  = 000001
  0 ^ 100000  = 100000

  i = 1
  v = 4 
  1 << 1 == 000010
  1 << 4 == 010000
  000001 ^ 000010  = 000011
  100000 ^ 010000  = 110000 

  i = 2
  v = 3 
  1 << 2 == 000100
  1 << 3 == 001000
  000011 ^ 000100  = 000111
  110000 ^ 001000  = 111000 
}
min = 3 
000111 << 3 == 111000
111000 === 111000

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

Предостережения здесь, конечно:

1. длина входного массива и максимальное значение массива ограничено максимальным значением для $x в ( 1 << $x > 0 )

2. Предельная эффективность зависит от того, как ваша базовая система реализует следующие возможности:

   1. сдвиг 1 бита на n позиций вправо.
   2. или 2 регистра. (где «регистры» могут, в зависимости от реализации, охватывать несколько регистров)

   редактировать Отмеченные выше утверждения кажутся запутанными. Предполагая идеальный компьютер, где "целое число" - это регистр с бесконечной точностью, который все еще может выполнить ^ b за O (1) времени.

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

• Насколько сложен 1 == 1 ?, конечно, каждый раз верно должно быть O (1) ?.
• А как насчет 2 ^ 32 == 2 ^ 32.
• O (1)? 2 ^ 33 == 2 ^ 33? Теперь у вас есть вопрос о размере регистра и базовой реализации.
• К счастью, XOR и == могут выполняться параллельно, поэтому, если принять допущение о бесконечной точности и машине, рассчитанной на бесконечную точность, можно с уверенностью предположить, что XOR и == принимают постоянное время независимо от их значения (потому что оно бесконечно ширина, он будет иметь бесконечное заполнение 0. Очевидно, что это не существует. Но также, изменение 000000 на 000100 не увеличивает использование памяти.
• Тем не менее, на некоторых машинах (1 << 32) << 1 <em>будет потреблять больше памяти, но сколько неясно.

Answer 5

Полагаю, вопрос сводится к тому, чтобы

(maximum - minimum + 1) == array_size

и, очевидно, это можно сделать за время O (N) и пространство O (1) следующим образом:

int check_range(int input[], int N){
    int max = -INFINITY, min = INFINITY, i;
    for(i=0; i<N; i++){
        if(input[i] < min) min=input[i];
        if(input[i] > max) max=input[i];
    }
    return (max - min + 1) == N;
}

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

Answer 6

Счетчик-пример для алгоритма XOR .

(не может опубликовать это как комментарий)

@ popopome

Для a = {0, 2, 7, 5,} возвращается true (означает, что a - это перестановка диапазона [0, 4)), но в этом случае он должен возвращать false (a, очевидно, не является перестановкой [0, 4)).

Другой пример счетчика: {0, 0, 1, 3, 5, 6, 6} - все значения находятся в диапазоне, но есть дубликаты.

Я мог неправильно реализовать идею (или тесты) popopome, поэтому вот код:

bool isperm_popopome(int m; int a[m], int m, int  n)
{
  /** O(m) in time (single pass), O(1) in space,
      no restrictions on n,
      no overflow,
      a[] may be readonly
  */
  int even_xor = 0;
  int odd_xor  = 0;

  for (int i = 0; i < m; ++i)
    {
      if (a[i] % 2 == 0) // is even
        even_xor ^= a[i];
      else
        odd_xor ^= a[i];

      const int b = i + n;
      if (b % 2 == 0)    // is even
        even_xor ^= b;
      else
        odd_xor ^= b;
    }

  return (even_xor == 0) && (odd_xor == 0);
}

Answer 7

Вот решение за O (N) времени и O (1) дополнительного пространства для поиска дубликатов: -

public static boolean check_range(int arr[],int n,int m) {

        for(int i=0;i<m;i++) {
            arr[i] = arr[i] - n;
            if(arr[i]>=m)
                return(false);
        }

        System.out.println("In range");

        int j=0;
        while(j<m) {
            System.out.println(j);
            if(arr[j]<m) {

                if(arr[arr[j]]<m) {

                    int t = arr[arr[j]];
                    arr[arr[j]] = arr[j] + m;
                    arr[j] = t;
                    if(j==arr[j]) {

                        arr[j] = arr[j] + m;
                        j++;
                    }

                }

                else return(false);

            }

            else j++;

        }

Объяснение: -

1. Привести число в диапазон (0, m-1) с помощью arr [i] = arr [i] - n, если выход за пределы диапазона возвращает false.
2. для каждого я проверяю, не занят ли arr [arr [i]], то есть имеет ли оно значение меньше m
3. если это так, поменяйте местами (arr [i], arr [arr [i]]) и arr [arr [i]] = arr [arr [i]] + m, чтобы указать, что он занят
4. если arr [j] = j и просто добавить m и увеличить j
5. если arr [arr [j]]> = m означает, что он занят, следовательно, текущее значение является дубликатом и, следовательно, возвращает false.
6. если arr [j]> = m, пропустить

Answer 8

Я не думаю, что вам вообще нужно использовать суммы. Просто проверьте минимальное и максимальное значения и проверьте на наличие дубликатов. Проверка на наличие дубликатов - сложная часть, так как вы не знаете заранее, поэтому вы не можете отсортировать за один проход. Чтобы обойти это, ослабьте условие в массиве (edit: destination). Вместо того, чтобы требовать его сортировки, перейдите к циклическому сдвигу отсортированной последовательности, чтобы массив получал [k, k + 1, ..., n + m-2, n + m-1, n, n + 1, ..., k-2, k-1] для некоторого k.

При условии, указанном выше, вы можете предположить, что a [0] уже находится в правильной позиции, тогда правильная позиция для элемента d равна (d-a[0]) mod m, предполагая индексирование массива с нуля. Например, с [4,?,?,?] Вы можете ожидать [4,5,6,7] или [4,1,2,3] или [4,5,6,3] или [4,5, 2,3].

Затем просто отсканируйте массив один раз, поместив каждый элемент в его рассчитанную позицию, обновив min и max и проверив наличие конфликтов. Если нет столкновений и max-min = m, то условие выполняется, иначе оно ложно.