分割和征服算法找到一个不重复的元素

Question

如果我有一个排序的整数列表，其中重复除一个元素之外的每个元素，我如何在不到O（n）的时间内找到单例元素？

例如：（（-2，-2、5、5、5、67、67、72、80、80、80、80）将返回72。

我相当确定此过程涉及二进制搜索，但不确定如何实现它。我只是在这里寻找伪代码。

我正在考虑遍历列表，并二进制搜索当前元素的最后一次出现。如果该索引与我们当前使用的索引相同，则为单例元素。如果没有，继续前进。我想那应该是O（nlogn）。

Answer 1

如果每个整数可以重复任意次数，则最佳算法为O(n)，因为无法避免迭代每个整数。只需简单地遍历列表，并保留一个计数器，该计数器可在一行中找到多少个相同的整数。如果计数器只有一个，并且发现了一个新的整数，则终止，因为我们发现了非重复整数。

如果知道所有数字重复相同的次数（不重复的数字除外），则可以使用二进制搜索来实现更好的时间复杂度。但是，根据您的示例问题，情况似乎并非如此。

Answer 2

O（n）Python实现：

def find_singletons(items):
    singletons = []
    a, b = items[:2]
    for item in items[2:]:
        if a != b and b != item:
            singletons.append(b)
        a, b = b, item
    return singletons


items = [-2, -2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80]
print(find_singletons(items))
# [72]

---

另一个O（n）Python实现（使用计数器）：

def find_singletons2(items):
    singletons = []
    count = 1
    last_item = items[0]
    for item in items[1:]:
        if last_item != item:
            if count == 1:
                singletons.append(last_item)
            count = 1
        else:
            count += 1
        last_item = item
    return singletons


items = [-2, -2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80]
print(find_singletons(items))
# [72]