从排序数组中查找小于O(n)的唯一数字

Question

我接受了采访,有以下问题:

在小于O(n)的时间内从排序的数组中查找唯一的数字.

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

我给出了解决方案,但那是O(n).

编辑: 排序的数组大小约为200亿,唯一数字约为1000.

Answer 1

我不认为它可以在少于O(n)的情况下完成.以数组包含的情况为例1 2 3 4 5:为了获得正确的输出,必须查看数组的每个元素,因此O(n).

Answer 2

分而治之:

• 查看排序序列的第一个和最后一个元素(初始序列是data[0]..data[data.length-1]).
• 如果两者相等,则序列中唯一的元素是第一个(无论序列有多长).
• 如果不同,则将序列分开并重复每个子序列.

在平均情况下以O(log(n))求解,而在最坏的情况下(当每个元素不同时)求解O(n).

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 3

如果您的大小排序数组n具有m不同的元素，您可以这样做O(mlogn)。

请注意，当m << n (eg m=2 and n=100)

算法：

初始化：当前元素y = first element x[0]

步骤1：对最后一次出现的yin x（可以及时完成O(log(n))。让它的索引为i

步骤2：y = x[i+1]然后转到步骤1

m = O(n)编辑：在这种算法效果不佳的情况下。为了缓解这个问题，您可以将其与常规算法并行运行O(n)。元算法由我的算法和O(n)并行运行的算法组成。当这两个算法中的任何一个完成时，元算法就会停止。