在不到O(n)的时间复杂度内从已排序的数组中找出唯一的数字

Question

我参加了一次面试，其中有以下问题:

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

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

我给出的解决方案时间复杂度为O(n)。

编辑：已排序数组大小约为200亿，唯一数字约为1000个。

- Deepu--Java

---

你至少需要知道最后一个元素，因此你必须遍历所有元素至少一次。因此，最小的下界是O(N)。 - coder hacker

如果新的“唯一”数字与最后一个索引上的数字相同，则跳出循环。因此，如果您到达第一个“3”，则可以停止循环。 - Tom

@Tom 这仍然是O(N)。 - coder hacker

@Tom，它仍然是线性的，与元素数量成正比，因此是O（N）。我希望你知道O（N）是什么意思？ - coder hacker

@Tom，BigOh O()符号是算法的最坏情况，与算法处理的数据无关。二分查找是O(log n)，因为只要数组排序，无论数组中的数据如何，您最多跳转O(log n)次。 - vz0

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

- Peter Walser

---

O(log n)并不是平均情况。只有在存在相对大量的重复时，它才是O(log n)（或更好）。在一般情况下，它是O(n)。 - Jim Mischel

你说得没错，但是这个解决方案可以在少于O(n)的时间内找到唯一的数字，因为它不一定需要查看所有数字。没有重复是最坏的情况，而不是平均情况。 - Peter Walser

@PeterWalser，我认为你的解决方案比其他人更好，并且与我编辑后的问题相符。在接受你的答案之前，让我检查其他输入。谢谢。 - Deepu--Java

@PeterWalser：我们对输入的分布了解甚少。你不能断言什么是或不是平均情况。 - Karoly Horvath

这个情况怎么样？[1,2]？ - Manish Kasera

根据OP提出的问题（200亿个数字，仅1000个唯一），我认为这种方法非常有效，并且可以在O(logn)时间内检索唯一元素。对于所有唯一元素的情况，无论如何都没有已知算法可以在小于O(n)的时间内解决。 - gaurav jain

Answer 2

我认为不可能在O(n)的时间内完成。以数组包含1 2 3 4 5为例：为了获得正确的输出，必须查看数组的每个元素，因此时间复杂度是O(n)。

- DanielGibbs

---

我同意你的观点，而且我也给出了相同的答案，但他告诉我这是可能的。这就是为什么我在这里寻找答案，因为我还没有弄清楚它是如何可能的。 - Deepu--Java

面试官可能对O(n)的理解有所不同，或者将库函数视为常数时间。 - DanielGibbs

你可以将复杂度作为其他因素的函数（例如数组中不同元素的数量）。请参见下面的答案。 - ElKamina

Answer 3

如果您的大小为n的排序数组具有m个不同元素，则可以完成O(mlogn)操作。

请注意，当m << n (例如m=2且n=100)时，这将非常高效。

算法：

初始化：当前元素y = 第一个元素x[0] 步骤1：在x中执行最后一次出现y的二进制搜索（可以在O(log(n))时间内完成）。将其索引命名为i 步骤2：y = x[i+1]并转到步骤1

编辑：在m = O(n)的情况下，该算法将表现糟糕。为了缓解这种情况，您可以与常规的O(n)算法并行运行。 元算法由我的算法和O(n)算法并行运行组成。 当这两个算法中的任何一个完成时，元算法停止。

- ElKamina

---

但它仍然不低于O(n)。 - Sopel

不是最坏的情况。但当m<<n（这是OP所暗示的）时，它小于O（n）。 - ElKamina

你说的没错，在某些情况下确实更快，但渐进复杂度不能仅在某个范围内进行比较。我知道你的意思，但这并不能解决所给出的问题。 - Sopel

稍微修改了一下。现在复杂度 <= O(n)。 - ElKamina

Answer 4

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

- Qiang Dai

---

在这个问题中使用分治法是一个有趣的想法。我的代码已经准备好运行了。分治部分有一点技巧，你必须避免重复元素出现在两侧。 - Qiang Dai

Answer 5

由于数据是整数，因此在任意两个值之间可能发生的唯一值是有限的。因此，首先查看数组中的第一个和最后一个值。如果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）并且在许多情况下更好”）。

- Michał Kosmulski

---

似乎您提供了顺序条目的解决方案，但也可能是1 55 55 1000这样的情况。 - Deepu--Java

@DeepakTiwari 原问题说明数组已排序。 - Michał Kosmulski

@DeepakTiwari 是的，对于 1、55、55、1000 这种情况确实没有优势，但我们关注的是渐近行为。如果这个序列中重复出现的数字“55”不只是两次，而是 100 次，那么完整的值集合所需的操作次数将比序列长度 102 少得多。 - Michał Kosmulski