从小于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

分而治之 ：

• 查看排序序列的第一个和最后一个元素（初始序列为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]);
    }
}