В менее чем линейном времени найдите дубликат в отсортированном массиве

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

Предположения

Массив отсортирован
Существует только один дубликат
Массив только, заполненный цифрами [0, n], где n - длина массива.

Пример массива: [0,1,2,3,4,5,6,7,8,8,9]

Я попытался придумать алгоритм разделения и покорения, чтобы решить эту проблему, но я не уверен, что это правильный ответ. У кого-нибудь есть идеи?

Ответ 1

Может быть выполнено в O (log N) с измененным двоичным поиском:

Начало в середине массива: если array [idx] < idx дубликат находится слева, в противном случае - вправо. Промыть и повторить.

Ответ 2

Если в массиве отсутствует число, как в примере, оно выполняется в O (log n) с двоичным поиском. Если a[i] < i, дубликат перед i, в противном случае - после i.

Если есть один номер, отсутствующий и один дубликат, мы все же знаем, что если a[i] < i дубликат должен быть до i, а если a[i] > i, отсутствующий номер должен быть до i и дублировать после. Однако, если a[i] == i, мы не знаем, остались ли недостающие числа и дубликаты до i или оба после i. В этом случае я не вижу пути для сублинейного алгоритма.

Ответ 3

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

Конечно, вы можете выполнить двоичный поиск.

Если arr[i/2] >= i/2, то дубликат находится в верхней половине массива, в противном случае он находится в нижней половине.

while (lower != upper)
    mid = (lower + upper) / 2
    if (arr[mid] >= mid)
        lower = mid
    else
        upper = mid-1

Так как массив между lower и upper уменьшается на половину на каждой итерации, алгоритм работает в O (log n).

демон ideone.com в Java

Ответ 4

Разница между суммой заданных элементов массива и суммой натуральных чисел от 0 до n-1 дает дублированный элемент. Сумма от 0 до n-1 элементов равна (N * N-1)/2 пример массива [0,1,2,3,4,5,6,7,8,8,9] сумма от 0 до 9 натуральных чисел: 45 сумма заданных элементов массива: 53 53-45 = 8 Кого является дублированный элемент

Ответ 5

Пример массива немного отличается от вашего вопроса. Поскольку n - длина массива, и в массиве есть один и только дубликат, значение каждого элемента в массиве должно быть в [0, n-1].

Если это так, то этот вопрос тот же, что и Как найти дублирующий элемент в массиве перетасованных последовательных целых чисел?

Следующий код должен найти дубликат в O (n) времени и O (1) пространстве.

public static int findOnlyDuplicateFromArray(int[] a, boolean startWithZero){
    int xor = 0;
    int offset = 1;
    for(int i=0; i < a.length; i++){
        if(startWithZero)
            xor = xor ^ (a[i] + offset) ^ i;
        else
            xor = xor ^ a[i] ^ i;
        }
        if(startWithZero)
            xor = xor - offset;
    return xor;
}

Ответ 6

Как насчет этого? (стиль рекурсии)

public static int DuplicateBinaryFind(int[] arr, int left, int right)
{
   int dup =0;

   if(left==right)
   {
      dup = left;
   }
   else
   {
        int middle = (left+right)\2;
        if(arr[middle]<middle)
        {
          dup = DuplicateBinaryFind(arr,left, middle-1);

        }
        else
        {
           dup = DuplicateBinaryFind(arr, middle+1, right);
        }
   }

   return dup;

}