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

Question

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

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

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

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

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

Answer 1

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

Начать с середины массива: если массив [idx]

Answer 2

Если в массиве нет пропущенных чисел, как в примере, это можно выполнить в O (log n) с помощью двоичного поиска.Если a[i] < i, то дубликат предшествует i, иначе - после i.

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

Answer 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

Answer 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 Что является дублированным элементом

Answer 5

#include <bits/stdc++.h>
using namespace std;

int find_only_repeating_element(int arr[] , int n){
int low = 0;
int high = n-1;
while(low <= high){
    int mid = low + (high - low)/2;
    if(arr[mid] == arr[mid + 1] || arr[mid] == arr[mid - 1]){
        return arr[mid];
    }
    if(arr[mid] < mid + 1){
        high = mid - 2;
    }else{
        low = mid + 1;
    }
   }
   return -1;
}

int main(int argc, char const *argv[])
{
int n , *arr;
cin >> n;
arr = new int[n];
for(int i = 0 ; i < n ; i++){
    cin >> arr[i];
}
    cout << find_only_repeating_element(arr , n) << endl;
    return 0;
}

Answer 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;

}

Answer 7

Пример массива немного отличается от вашего вопроса. Поскольку 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;
}