从查找排序数组的唯一号码，在不到为O（n） [英] Finding unique numbers from sorted array in less than O(n)

问题描述

我有一次采访，并有一个问题。查找不到O（n）的时间从排序的数组唯一的编号。

I had an interview and there was a question. Find unique numbers from sorted array in less than O(n) time.

 Ex: 1 1 1 5 5 5 9 10 10
 o/p 1 5 9 10

我给的解决方案，但是这是为O（n）。任何人都可以帮我这个线程。

I gave the solution but that was of O(n). Can anyone help me with this thread.

编辑：排序数组大小约20个十亿，独特的数字是大约1000

Sorted array size is approx 20 billion and unique numbers are approx 1000.

推荐答案

分而治之

• 看一个排序序列的第一个和最后一个元素（初始序列是数据[0] ..数据[data.length-1] ）。
• 如果二者相等，则序列中的唯一的元件是第一个（不管序列有多长）。
• 如果的不同，划分顺序和重复每个序列。

• look at the first and last element of a sorted sequence (the initial sequence is data[0]..data[data.length-1]).
• If both are equal, the only element in the sequence is the first (no matter how long the sequence is).
• If the are different, divide the sequence and repeat for each subsequence.

解决了 O（日志（N））在平均情况下，和O（N）仅在最坏的情况下（当每个元素都是不同的）。

Solves in O(log(n)) in the average case, and O(n) only in the worst case (when each element is different).

Java的code：

Java code:

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]);
    }
}

这篇关于从查找排序数组的唯一号码，在不到为O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！