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

При допущении, что числа меньше одного не допускаются и нет дубликатов, для этого существует простое тождество суммирования - сумма чисел от 1 до m с шагом 1 равна (m * (m + 1)) / 2 , Затем вы можете суммировать массив и использовать эту идентичность.

Вы можете узнать, есть ли дублирование по вышеуказанным гарантиям, плюс гарантия, что число не больше m или меньше n (что можно проверить в O(N))

Идея в псевдокоде:
0) Начните с N = 0
1) Возьмите N-й элемент в списке.
2) Если он не в нужном месте, если список был отсортирован, проверьте, где он должен быть.
3) Если место, где оно должно быть, уже имеет такой же номер, у вас есть дубликата - ВОЗВРАТ ИСТИНА
4) В противном случае поменяйте местами номера (чтобы поставить первое число в нужном месте).
5) С номером, который вы только что поменяли местами, он в нужном месте?
6) Если нет, вернитесь к шагу два.
7) В противном случае начните с первого шага с N = N + 1. Если это будет за концом списка, у вас не будет дупликов.

И, да, он работает в O(N), хотя может выглядеть как O(N ^ 2)

Примечание для всех (материал взят из комментариев)

Это решение работает в предположении, что вы можете изменить массив, а затем использовать сортировку Radix на месте (которая достигает скорости O(N)).

Были предложены другие математические решения, но я не уверен, что какое-либо из них было доказано. Существует множество сумм, которые могут быть полезны, но большинство из них сталкиваются с увеличением числа битов, необходимых для представления суммы, что нарушит постоянную гарантию дополнительного пространства. Я также не знаю, способен ли какой-либо из них произвести различное число для данного набора чисел. Я думаю, что может сработать сумма квадратов, которая имеет известную формулу для ее вычисления (см. Wolfram's )

Новое понимание (ну, больше размышлений, которые не помогают решить его, но интересны, и я иду спать):

Итак, упомянуто, возможно, использование суммы + суммы квадратов. Никто не знал, сработало ли это или нет, и я понял, что это становится проблемой только тогда, когда (x + y) = (n + m), как, например, факт 2 + 2 = 1 + 3. Квадраты также имеют эту проблему благодаря Пифагорейские тройки (поэтому 3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2, а сумма квадратов не работает). Если мы используем последнюю теорему Ферма , мы знаем, что это не может произойти при n ^ 3. Но мы также не знаем, существует ли x + y + z = n для этого (если мы не знаем, и я этого не знаю). Так что никаких гарантий, что это тоже не сломается - и если мы продолжим этот путь, у нас быстро кончатся биты.

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

---

Должен сказать, что найти контрпримеры иногда намного проще, чем доказать! Рассмотрим следующие последовательности, каждая из которых имеет сумму 28 и сумму квадратов 140:

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

Я не смог найти таких примеров длины 6 или меньше. Если вы хотите, чтобы пример имел правильные значения min и max, попробуйте этот пример длиной 8:

[1, 3, 3, 4, 4, 5, 8, 8]

---

Более простой подход (изменение идеи Хаззена):

Целочисленный массив длины m содержит все числа от n до n + m-1 ровно один раз, если

• каждый элемент массива находится между n и n + m-1
• дубликатов нет

(Причина: в данном целочисленном диапазоне есть только m значений, поэтому, если массив содержит m уникальных значений в этом диапазоне, он должен содержать каждое из них один раз)

Если вам разрешено изменять массив, вы можете проверить оба за один проход по списку с помощью модифицированной версии идеи алгоритма Хаззена (нет необходимости выполнять суммирование):

• Для всех индексов массива от 0 до m-1 сделать
  1. Если массив [i] = n + m => RETURN FALSE («найдено значение вне диапазона»)
  2. Рассчитать j = массив [i] - n (это позиция массива [i] на основе 0 в отсортированном массиве со значениями от n до n + m-1)
  3. Хотя j не равно i
     1. Если list [i] равен list [j] => RETURN FALSE («найден дубликат»)
     2. Обмен списками [i] со списком [j]
     3. Пересчитать j = массив [i] - n
• ВОЗВРАТ ИСТИНА

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

Answer 2

Работая с a[i] % a.length вместо a[i], вы сводите проблему к необходимости определить, что у вас есть числа 0 до a.length - 1.

Мы принимаем это наблюдение как должное и пытаемся проверить, содержит ли массив [0, m).

Найдите первый узел, который находится не в правильном положении, например,

0 1 2 3 7 5 6 8 4 ;     the original dataset (after the renaming we discussed)
        ^
        `---this is position 4 and the 7 shouldn't be here

Поменяйте это число на то, где оно должно быть . то есть поменяйте 7 на 8:

0 1 2 3 8 5 6 7 4 ; 
        |     `--------- 7 is in the right place.
        `--------------- this is now the 'current' position

Теперь мы повторяем это. Снова глядя на нашу текущую позицию, мы спрашиваем:

"это правильный номер для здесь?"

• Если нет, мы меняем его на правильное место.
• Если оно в нужном месте, мы двигаемся вправо и делаем это снова.

Снова следуя этому правилу, получим:

0 1 2 3 4 5 6 7 8 ;     4 and 8 were just swapped

Это будет постепенно составлять список правильно слева направо, и каждое число будет перемещаться не более одного раза, и, следовательно, это O (n).

Если есть дубликаты, мы заметим это, как только будет предпринята попытка поменять число backwards в списке.

Answer 3

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

Более простой метод:

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

Шаг 2, итерация по списку, отслеживание элементов низший и наивысший .

Шаг 3, (самый высокий - самый низкий) равен m? Если это так, верните true.

Answer 4

Любой однопроходный алгоритм требует омега (n) бит памяти.

Предположим противное, что существует однопроходный алгоритм, который использует o (n) битов. Поскольку он делает только один проход, он должен суммировать первые n / 2 значения в o (n) пространстве. Поскольку существует C (n, n / 2) = 2 ^ Theta (n) возможных наборов значений n / 2, взятых из S = {1, ..., n}, существуют два различных набора A и B для n / 2 значения, так что состояние памяти одинаково после обоих. Если A '= S \ A является «правильным» набором значений для дополнения A, то алгоритм не может правильно ответить для входных данных

A A '- да

B A '- нет

, поскольку он не может отличить первый случай от второго.

1011 * что и требовалось доказать *

Answer 5

Реализация алгоритма Хаззена в C

#include<stdio.h>

#define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];

int check_ntom(int a[], int n, int m) {
    int i = 0, j = 0;
    for(i = 0; i < m; i++) {
        if(a[i] < n || a[i] >= n+m) return 0;   //invalid entry
        j = a[i] - n;
        while(j != i) {
            if(a[i]==a[j]) return -1;           //bucket already occupied. Dupe.
            swapxor(a, i, j);                   //faster bitwise swap
            j = a[i] - n;
            if(a[i]>=n+m) return 0;             //[NEW] invalid entry
        }
    }
    return 200;                                 //OK
}

int main() {
    int n=5, m=5;
    int a[] = {6, 5, 7, 9, 8};
    int r = check_ntom(a, n, m);
    printf("%d", r);
    return 0;
}

Редактировать: изменение, внесенное в код для устранения незаконного доступа к памяти.

Answer 6

boolean determineContinuousArray(int *arr, int len)
{
    // Suppose the array is like below:
    //int arr[10] = {7,11,14,9,8,100,12,5,13,6};
    //int len = sizeof(arr)/sizeof(int);

    int n = arr[0];

    int *result = new int[len];
    for(int i=0; i< len; i++)
            result[i] = -1;
    for (int i=0; i < len; i++)
    {
            int cur = arr[i];
            int hold ;
            if ( arr[i] < n){
                    n = arr[i];
            }
            while(true){
                    if ( cur - n >= len){
                            cout << "array index out of range: meaning this is not a valid array" << endl;
                            return false;
                    }
                    else if ( result[cur - n] != cur){
                            hold = result[cur - n];
                            result[cur - n] = cur;
                            if (hold == -1) break;
                            cur = hold;

                    }else{
                            cout << "found duplicate number " << cur << endl;
                            return false;
                    }

            }
    }
    cout << "this is a valid array" << endl;
    for(int j=0 ; j< len; j++)
            cout << result[j] << "," ;
    cout << endl;
    return true;
}

Answer 7

Некоторое время назад я услышал об очень умном алгоритме сортировки от кого-то, кто работал в телефонной компании. Им пришлось отсортировать огромное количество телефонных номеров. Пройдя через множество различных стратегий сортировки, они наконец нашли очень элегантное решение: они просто создали битовый массив и обработали смещение в битовом массиве как номер телефона. Затем они просматривали свою базу данных за один проход, меняя бит для каждого числа на 1. После этого они просматривали битовый массив один раз, выплевывая номера телефонов для записей, для которых был установлен высокий бит.

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

Я собираюсь на время опустить параметр n, b / c, который просто запутывает вещи - добавить смещение индекса довольно просто.

Рассмотрим:

for i = 0 to m
  if (a[a[i]]==a[i]) return false; // we have a duplicate
  while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i)
  sum = sum + a[i]
next

if sum = (n+m-1)*m return true else return false

Это не O (n) - возможно, ближе к O (n Log n) - но оно обеспечивает постоянное пространство и может обеспечить другой вектор атаки для проблемы.

Если мы хотим O (n), то использование массива байтов и некоторых битовых операций обеспечит проверку дублирования с дополнительными n / 32 байтами используемой памяти (при условии, конечно, 32-битных байтов).

РЕДАКТИРОВАТЬ: вышеупомянутый алгоритм может быть улучшен дополнительно, добавив проверку суммы во внутреннюю часть цикла, и проверьте:

if sum > (n+m-1)*m return false

таким образом, он быстро потерпит неудачу.

Answer 8

Вот рабочий раствор в O (n)

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

function testArray($nums, $n, $m) {
    // check the sum. PHP offers this array_sum() method, but it's
    // trivial to write your own. O(n) here.
    if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) {
        return false;    // checksum failed.
    }
    for ($i = 0; $i < $m; ++$i) {
        // check if the number is in the proper range
        if ($nums[$i] < $n || $nums[$i] >= $n + $m) {
            return false;  // value out of range.
        }

        while (($shouldBe = $nums[$i] - $n) != $i) {
            if ($nums[$shouldBe] == $nums[$i]) {
                return false;    // duplicate
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$shouldBe];
            $nums[$shouldBe] = $temp;
        }
    }
    return true;    // huzzah!
}

var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5));  // true
var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5));  // true
var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5));  // false - out of range
var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5));  // false - checksum fail
var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5));  // false - dupe
var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true

Answer 9

Если вы знаете только длину массива и вам разрешено изменять массив, это можно сделать в пространстве O (1) и времени O (n).

Процесс состоит из двух простых шагов. 1. «Модульная сортировка» массива. [5,3,2,4] => [4,5,2,3] (O (2n)) 2. Убедитесь, что сосед каждого значения на единицу выше, чем он сам (по модулю) (O (n))

Все сказали, что вам нужно максимум 3 прохода через массив.

Сортировка по модулю - сложная часть, но цель проста. Возьмите каждое значение в массиве и сохраните его по собственному адресу (по модулю длины). Это требует одного прохода через массив, циклически проходя по каждому местоположению, «вытесняя» его значение, меняя его в правильное местоположение и перемещая в значение в месте назначения. Если вы когда-либо добавите значение, которое соответствует значению, которое вы только что выселили, у вас есть дубликат, и вы можете выйти досрочно. В худшем случае это O (2n).

Проверка - это один проход массива, проверяющий каждое значение со своим ближайшим соседом. Всегда O (n).

Комбинированный алгоритм: O (n) + O (2n) = O (3n) = O (n)

Псевдокод из моего решения:

foreach(values[]) 
  while(values[i] not congruent to i)
    to-be-evicted = values[i]
    evict(values[i])   // swap to its 'proper' location
    if(values[i]%length == to-be-evicted%length)
      return false;  // a 'duplicate' arrived when we evicted that number
  end while
end foreach
foreach(values[])
  if((values[i]+1)%length != values[i+1]%length)
    return false
end foreach

Я включил ниже подтверждение концепции Java-кода, оно не очень красивое, но оно проходит все модульные тесты, которые я сделал для него. Я называю их «StraightArray», потому что они соответствуют покерной руке стрита (непрерывная последовательность, игнорирующая масти).

public class StraightArray {    
    static int evict(int[] a, int i) {
        int t = a[i];
        a[i] = a[t%a.length];
        a[t%a.length] = t;
        return t;
    }
    static boolean isStraight(int[] values) {
        for(int i = 0; i < values.length; i++) {
            while(values[i]%values.length != i) {
                int evicted = evict(values, i);
                if(evicted%values.length == values[i]%values.length) {
                    return false;
                }
            }
        }
        for(int i = 0; i < values.length-1; i++) {
            int n = (values[i]%values.length)+1;
            int m = values[(i+1)]%values.length;
            if(n != m) {
                return false;
            }
        }
        return true;
    }
}

Answer 10

Проголосуйте, если я ошибаюсь, но я думаю, что мы можем определить, есть ли дубликаты или нет, используя дисперсию. Поскольку мы заранее знаем среднее значение (n + (m-1) / 2 или что-то в этом роде), мы можем просто суммировать числа и квадрат разности, чтобы определить, соответствует ли сумма уравнению (mn + m (m-1). ) / 2) и дисперсия (0 + 1 + 4 + ... + (m-1) ^ 2) / m. Если разница не совпадает, скорее всего, у нас есть дубликат.

РЕДАКТИРОВАТЬ: дисперсия должна быть (0 + 1 + 4 + ... + [(m-1) / 2] ^ 2) * 2 / м, потому что половина элементов меньше среднего, а другая половина больше среднего.

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