从排序列表中获取唯一元素的最有效方法是什么？

Question

我想知道是否有人知道一些真正有效的方法如何从排序列表中获取所有唯一的数字。示例：如果我有 list = [1,1,2,3,3,3,6,6,8,10,100,180,180] 我想得到一个像这样的列表 [1,2,3,6,7,10,100,180]。我正在寻找一种比遍历整个列表更有效的解决方案，其复杂度优于 O(n)。

我的第一个想法是检查每隔一个数字，但它不起作用。 这是我的代码：

solution = []
i = 0
while i < values.size() - 2:
    if values.get(i) == values.get(i + 2):
        if values.get(i) not in solution:
            solution.append(values.get(i))
    else:
        if values.get(i) not in solution:
                solution.append(values.get(i))
                
        if values.get(i + 1) != values.get(i + 2) \
            and values.get(i) != values.get(i + 1):
            solution.append(values.get(i + 1))
        solution.append(values.get(i + 2))
    i += 2
    
if values.get(values.size() - 1) not in solution:
    solution.append(values.get(values.size() - 1))
return solution

Answer 1

令

k

为不同元素的数量， 和

n

元素总数。

从排序列表中获取所有唯一数字 [with] ... 复杂度优于 O(n)。

在一般情况下，显然你不能，因为

k

可能 是

n

的一部分，甚至与

n

一样大。 这里确实似乎至少有两度的回旋余地。

计数排序

首先，这个排序列表是如何产生的？ 也许它是使用某种比较排序构建的， 成本为 O(n log n)。 但也许我们知道元素的范围是有限的， 我们选择使用构建列表 计数排序, 时间复杂度为 O(n)，内存复杂度为 O(k)。

在这种情况下，保留那些

k

计数器， 并读出它们对应的元素值， 时间复杂度为 O(k)。 所以不是输入“列表”， 我们也接受计数器数据结构。

二分查找

当我们顺序扫描所有

n

元素时 我们将遇到

k

“突破”，我们将在其中前进 到一个全新的元素价值。 我们可以一分为二来找到这样的断裂点。

考虑退化的情况。 也许这些元素都对应“女”和“男”， 该应用程序是在女子学校使用的，所以 该列表表明我们有

n

女性。 显然我们可以在 O(1) 常数时间内区分这种情况， 通过检查第一个和最后一个元素并依赖单调输入。

我们去一所公立学校再试一次。 结果发现第一个元素和最后一个元素有一个不同， 我们将列表的开始称为“第一次中断”。 我们需要找到一个突破口。申请 二分查找 以通常的方式，时间复杂度为 O(log n)。

在

k << n

仍然成立的更一般环境中， 我们可以在 O(k log n) 时间内找到

k

中断， 内存复杂度为 O(k)。