Поиск уникальных номеров из отсортированного массива меньше, чем O (N)

Question

у меня было интервью, и там был следующий вопрос:

Найти уникальные номера из отсортированного массива меньше, чем O (N) времени.

Ex: 1 1 1 5 5 5 9 10 10 
Output: 1 5 9 10 

Я дал решение, но это было из O (N).

Edit: Сортировано размер массива составляет около 20 млрд уникальных номера около 1000.

Answer 1

и властвуй:

• взгляд на первый и последний элемент в отсортированной последовательности (начальная последовательность data[0]..data[data.length-1]).
• Если оба равны, единственным элементом в последовательности является первый (независимо от того, как долго длится последовательность).
• Если они разные, разделите последовательность и повторите для каждой подпоследовательности.

Решает в O (журнал (п)) в среднем случае, и О (п) только в самом худшем случае (когда каждый элемент отличается).

код Java:

public static List<Integer> findUniqueNumbers(int[] data) { 
    List<Integer> result = new LinkedList<Integer>(); 
    findUniqueNumbers(data, 0, data.length - 1, result, false); 
    return result; 
} 

private static void findUniqueNumbers(int[] data, int i1, int i2, List<Integer> result, boolean skipFirst) { 

    int a = data[i1]; 
    int b = data[i2]; 

    // homogenous sequence a...a 
    if (a == b) { 
     if (!skipFirst) { 
      result.add(a); 
     } 
    } 
    else { 
     //divide & conquer 
     int i3 = (i1 + i2)/2; 
     findUniqueNumbers(data, i1, i3, result, skipFirst); 
     findUniqueNumbers(data, i3 + 1, i2, result, data[i3] == data[i3 + 1]); 
    } 
} 

Answer 2

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

Answer 3

Поскольку данные состоят из целых чисел, существует конечное число уникальных значений, которые могут возникать между любыми двумя значениями. Итак, начните с рассмотрения первого и последнего значения в массиве. Если a[length-1] - a[0] < length - 1, будут некоторые повторяющиеся значения. Поместите a[0] и a[length-1] в контейнер с постоянным доступом, как хэш-набор. Если два значения равны, вы знаете, что в массиве есть только одно уникальное значение, и вы закончили. Вы знаете, что массив отсортирован. Итак, если два значения отличаются друг от друга, вы можете посмотреть на средний элемент. Если средний элемент уже находится в наборе значений, вы знаете, что можете пропустить всю левую часть массива и рекурсивно анализировать правую часть. В противном случае проанализируйте левую и правую части рекурсивно.

В зависимости от данных в массиве вы сможете получить набор всех уникальных значений в другом количестве операций. Вы получаете их в постоянное время O(1), если все значения совпадают, так как вы будете знать это после проверки только первого и последнего элементов. Если «относительно мало» уникальных значений, ваша сложность будет близка к O(log N), потому что после каждого раздела вы «довольно часто» сможете выбросить хотя бы половину анализируемого подматрица. Если значения уникальны и a[length-1] - a[0] = length - 1, вы также можете «определить» набор в постоянное время, поскольку они должны быть последовательными числами от a[0] до a[length-1]. Однако, чтобы фактически перечислить их, вам нужно будет вывести каждое число, и их будет N.

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

Answer 4

Если отсортированный массив размера n имеет m отдельных элементов, вы можете сделать O(mlogn).

Обратите внимание, что это будет эффективно, когда m << n (eg m=2 and n=100)

Алгоритм:

Initialization: Текущий элемент y = first element x[0]

Шаг 1: Сделайте двоичный поиск последнего вхождения y в x (может быть сделано в O(log(n)).Существует индекс i

Шаг 2: y = x[i+1] и перейдите к шагу 1

Редактировать: В тех случаях, когда m = O(n) этот алгоритм будет работать плохо. Чтобы облегчить его, вы можете запустить его параллельно с обычным алгоритмом O(n). Мета-алгоритм состоит из моего алгоритма и алгоритма O(n), работающего параллельно. Мета-алгоритм останавливается при завершении любого из этих двух алгоритмов.

Answer 5

import java.util.*; 

/** 
* remove duplicate in a sorted array in average O(log(n)), worst O(n) 
* @author XXX 
*/ 
public class UniqueValue { 
    public static void main(String[] args) { 
     int[] test = {-1, -1, -1, -1, 0, 0, 0, 0,2,3,4,5,5,6,7,8}; 
     UniqueValue u = new UniqueValue(); 
     System.out.println(u.getUniqueValues(test, 0, test.length - 1)); 
    } 

    // i must be start index, j must be end index 
    public List<Integer> getUniqueValues(int[] array, int i, int j) { 
     if (array == null || array.length == 0) { 
      return new ArrayList<Integer>(); 
     } 
     List<Integer> result = new ArrayList<>(); 
     if (array[i] == array[j]) { 
      result.add(array[i]); 
     } else { 
      int mid = (i + j)/2; 
      result.addAll(getUniqueValues(array, i, mid)); 

      // avoid duplicate divide 
      while (mid < j && array[mid] == array[++mid]); 
      if (array[(i + j)/2] != array[mid]) { 
       result.addAll(getUniqueValues(array, mid, j)); 
      } 
     } 
     return result; 
    } 
}