当所有其他值相同时，找到一个唯一值的最快方法

我已经解决了这个问题，我想知道最快的解决方法是什么。 />示例：

 find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

我想出了解决方案：

 -override“> from collections import Counter

def find_uniq(arr):
    nums = list(Counter(arr).items())
    data = [i for i in nums if i[1] == 1]
    return data[0][0]

我决定使用Counter，因为我觉得使用起来很舒服，但是当看别人回答一些使用集而别人也使用计数器时。足够，哪种方法可以解决这个问题，从而导致最快的时间复杂度？

对于[0，1]，该返回什么？

@Cireo如tinstaafl所述：“挑战至少要保证3个元素。如果只有2个元素，您怎么知道哪个是唯一的”

“有一个数组，其中包含一些数字。除一个数字外，其他所有数字均相等。尝试找到它！”如果arr [0] == arr [1]和arr [0]！= arr [2]返回arr [2]否则返回“我尝试过”

#1 楼

到目前为止，有关解决方案的一件事是，它们都需要至少对所有元素进行一次迭代。
使用迭代方法可以使您在找到唯一项时缩短回路。像这样的方法会起作用：

def find_uniq(arr):
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            if i == 0 and arr[i] != arr[i + 2]:
                return arr[i]
            return arr[i + 1]]

进行了一些思考，并提出了一个优化方法，该方法可以显着缩短时间： n）数组的长度-1.

\ $ \ begingroup \ $
如果您的代码得到一个2元素数组，它将访问arr [2]，该数组超出范围。
\ $ \ endgroup \ $
–罗兰·伊利格（Roland Illig）
20 Jul 25'7:09

\ $ \ begingroup \ $
挑战至少要保证3个要素。如果只有2个，怎么知道哪个唯一
\ $ \ endgroup \ $
–tinstaafl
20年7月25日在7:11

\ $ \ begingroup \ $
该答案的答案为[0，1，0，0，1，2]。您将始终需要阅读整个列表，因为唯一元素可能始终是最后一个。
\ $ \ endgroup \ $
– Turksarama
20 Jul 25'9:47

\ $ \ begingroup \ $
@Turksarama这是无效的输入，因为“除一个数字外，所有数字均相等”。该代码适用于[0,0,2]。
\ $ \ endgroup \ $
– MT0
20年7月25日在10:01

\ $ \ begingroup \ $
令人失望的是，目前为止最慢的解决方案获得最多的票数并被接受。请参阅基准。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年7月25日在17:24

#2 楼

基准！具有一千或一百万个元素的列表的基准，其唯一元素位于数组的中间，以反映“典型” /“平均”情况。结果是时间，因此要降低=更快。

n=1000
0.90 find_uniq_Jacques
1.18 find_uniq_tinstaafl_1
0.59 find_uniq_tinstaafl_2
0.88 find_uniq_GZ0_1
0.14 find_uniq_GZ0_2
0.88 find_uniq_Peilonrayz
0.22 find_uniq_RootTwo
0.26 find_uniq_HeapOverflow_1
0.28 find_uniq_HeapOverflow_2
0.26 find_uniq_HeapOverflow_3
0.09 find_uniq_HeapOverFlow_Codewars
0.06 find_uniq_HeapOverflow_GZ0
0.57 unique_different_ethiy
0.28 find_uniq_KyleG_1
0.25 find_uniq_KyleG_2

n=1000000
0.94 find_uniq_Jacques
1.36 find_uniq_tinstaafl_1
0.68 find_uniq_tinstaafl_2
0.99 find_uniq_GZ0_1
0.19 find_uniq_GZ0_2
0.98 find_uniq_Peilonrayz
0.19 find_uniq_RootTwo
0.23 find_uniq_HeapOverflow_1
0.26 find_uniq_HeapOverflow_2
0.25 find_uniq_HeapOverflow_3
0.09 find_uniq_HeapOverFlow_Codewars
0.04 find_uniq_HeapOverflow_GZ0
0.57 unique_different_ethiy
0.28 find_uniq_KyleG_1
0.22 find_uniq_KyleG_2

在Windows 10 64位上使用Python 3.8.1 32位完成。
基准代码：

from timeit import timeit
from collections import Counter
from itertools import groupby

solutions = []
def register(solution):
    solutions.append(solution)
    return solution

@register
def find_uniq_Jacques(arr):
    nums = list(Counter(arr).items())
    data = [i for i in nums if i[1] == 1]
    return data[0][0]

@register
def find_uniq_tinstaafl_1(arr):
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            if i == 0 and arr[i] != arr[i + 2]:
                return arr[i]
            return arr[i + 1]

@register
def find_uniq_tinstaafl_2(arr):
    for i in range(0,len(arr) - 1, 2):
        if arr[i] != arr[i+1]:
            if i == 0:
                if arr[i] != arr[i + 2]:
                    return arr[i]
                return arr[i + 1]
            else:
                if arr[i] != arr[i-1]:
                    return arr[i]
                return arr[i + 1]
    return arr[-1]

@register
def find_uniq_GZ0_1(arr):
    return next(k for k, freq in Counter(arr).items() if freq == 1)

@register
def find_uniq_GZ0_2(arr):
    group_iter = groupby(arr)
    k1, g1 = next(group_iter)
    c1 = len(list(g1))
    k2, g2 = next(group_iter)
    if c1 > 1:
       # Group g1 has more than one element
       return k2
    try:
       # Group g2 has more than one element
       next(g2)
       next(g2)
       return k1
    except StopIteration:
       # Both g1 and g2 has one element
       return k2 if next(group_iter)[0] == k1 else k1

@register
def find_uniq_Peilonrayz(arr):
    return Counter(arr).most_common()[-1][0]

@register
def find_uniq_RootTwo(arr):
    a, b = set(arr)
    return a if arr[:3].count(a) < 2 else b

@register
def find_uniq_HeapOverflow_1(arr):
    a = arr[0]
    if a not in arr[1:3]:
        return a
    for b in arr:
        if b != a:
            return b

@register
def find_uniq_HeapOverflow_2(arr):
    dupe = sorted(arr[:3])[1]
    for x in arr:
        if x != dupe:
            return x

@register
def find_uniq_HeapOverflow_3(arr):
    a = arr[0]
    for b in arr:
        if b != a:
            return b if a in arr[1:3] else a

@register
def find_uniq_HeapOverFlow_Codewars(arr):
    arr.sort()
    return arr[-(arr[0] == arr[1])]

@register
def find_uniq_HeapOverflow_GZ0(arr):
    group_iter = groupby(arr)
    k1, _ = next(group_iter)
    k2, g2 = next(group_iter)
    next(g2)
    return k1 if k2 in g2 else k2

@register
def unique_different_ethiy(iterable):
    # assert isinstance(iterable, Iterable)
    # assert len(iterable) > 2
    if iterable[0] != iterable[1]:
        return iterable[0] if iterable[1] == iterable[2] else iterable[1]
    else:
        for element in iterable[2:]:
            if element != iterable[1]:
                return element

@register
def find_uniq_KyleG_1(arr):
    common = arr[0]
    if common not in arr[1:3]:
        return common
    for a, b in zip(arr[1::2], arr[2::2]):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

@register
def find_uniq_KyleG_2(arr):
    iterator = iter(arr)
    common = next(iterator)
    if common not in arr[1:3]:
        return common
    for a, b in zip(iterator, iterator):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

# Run the benchmarks
for e in 3, 6:
    n = 10**e
    number = 10**(7 - e)  # fewer number of runs for larger n
    print(f'{n=}')
    arr = [0] * n
    arr[n // 2] = 1

    # Repeat round-robin to reduce effects of CPU speed changes etc
    timeses = [[] for _ in solutions]
    for i in range(20):
        for solution, times in zip(solutions, timeses):
            arrs = iter([arr[:] for _ in range(number)])
            t = timeit(lambda: solution(next(arrs)), number=number)
            times.append(t)
        print(i, end=' ')
    print()
    for solution, times in zip(solutions, timeses):
        print('%.2f' % min(times), solution.__name__)
    print()

\ $ \ begingroup \ $
谢谢您的比较，我也很好奇。
\ $ \ endgroup \ $
–雅克
20 Jul 25'20:10

\ $ \ begingroup \ $
感谢您改进我的解决方案和基准测试工作。由于早期退出解决方案的运行时间取决于专有元素的位置，因此最好测试不同种类的输入。更具体地说，您可以进行三种测试并输出相应的运行时：（1）最佳情况：可分辨元素出现在开始；（2）最坏情况：可分辨元素出现在末尾；（3）平均情况：生成所有可能的输入（即，对于区分元素的每个出现位置，一个输入）并取平均运行时间。
\ $ \ endgroup \ $
– GZ0
20/07/25在22:52

\ $ \ begingroup \ $
@HeapOverflow（1）最佳情况场景是相关的，因为在这些情况下，tinstaafl的迭代解决方案应该排名更高。（2）最坏的情况也可能导致不同的排名。同时，它们反映了实现开销的差异，这与选择早期退出所导致的差异无关。如果您没有太多时间，则只显示平均情况即可。但是，您需要非常谨慎地得出结论，并明确提到获胜者是基于平均情况下运行时的比较。
\ $ \ endgroup \ $
– GZ0
20 Jul 26'0:50

\ $ \ begingroup \ $
@ GZ0是的，最好的情况与确定谁在最好的情况下最快是“相关的”。但是谁在乎呢？这些最佳情况无关紧要，即使发生了，对整个时间的贡献也很小。所以它们无关紧要²:-)是的，最坏情况应该导致不同的排名，但是同样，复杂度级别对于平均和最坏情况是相同的，最坏情况应该只花两倍的时间，因此最坏情况真的不是那么有趣。在我看来，我们关心的是最坏的情况，因为它既现实又实际地发生并且具有灾难性。我曾有一个 ...
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年7月26日在10:58

\ $ \ begingroup \ $
...再次，因素2。即使您确实有理由认为分布严重偏向最坏情况，也不是很有趣。对于蒂姆索尔（Timsort），我们有理由相信“最佳情况”确实会发生。正如Wikipedia所说，“ Timsort旨在利用大多数现实世界数据中已经存在的连续有序元素的运行”。除了这种“现实世界的数据”之外，它还可以应对像这样的少量编码挑战，其中所有允许的输入都是Timsort的最佳情况。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20 Jul 26'14:12

#3 楼

无论数组如何遍历，可分辨元素都可以在遍历结束时出现。因此，有必要在最坏的情况下遍历整个数组，并且不存在比\ $ n \ $具有更好的最坏情况时间复杂度的算法。但是，实际上，可以改善实现的实际运行时间以及平均情况下的时间复杂度。
首先，您的解决方案将Counter(arr)的键值对转换为列表。假设输入格式正确，则无需进行此转换，因为它足以返回具有对应频率值1的第一个键。改进的实现如下：

def find_uniq(arr):
    return next(k for k, freq in Counter(arr).items() if freq == 1)

其次，创建一个Counter需要遍历整个输入阵列。在大多数情况下，可以通过找到可分辨元素返回来避免这种情况，如前面的答案中所述。这种方法将平均情况下的时间复杂度提高了2倍。请注意，如果使用\ $ O（\ cdot）\ $和\ $ \ Theta（\ cdot）\ $表示法来描述时间复杂度，则不会区别在于，由于给定输入大小，这些表示法仅表示运行时间增长的渐近顺序。可以在此处找到更多说明。
此改进方法的特定于Python的有效实现是使用itertools.groupby函数，如下所示。它避免了Python中的显式for -loop，这通常比基于隐式循环的实现（例如Counter(arr)）要慢。

from itertools import groupby

def find_uniq(arr):
    group_iter = groupby(arr)
    k1, g1 = next(group_iter)
    c1 = len(list(g1))
    k2, g2 = next(group_iter)
    if c1 > 1:
       # Group g1 has more than one element
       return k2
    try:
       # Group g2 has more than one element
       next(g2)
       next(g2)
       return k1
    except StopIteration:
       # Both g1 and g2 has one element
       return k2 if next(group_iter)[0] == k1 else k1

更新：@HeapOverflow在他的回答中提供了此实现的改进版本。

\ $ \ begingroup \ $
O（n-1）怎么样？那比O（n）好。
\ $ \ endgroup \ $
–tinstaafl
20/07/25在7:14

\ $ \ begingroup \ $
@tinstaafl O（n-1）与O（n）相同。如果算法为O（n），则意味着当n足够大时，运行时受输入大小n的线性函数的上限限制。 2n和0.01n的实际运行时间均为O（n）。我已经对答案进行了编辑，以使其更加准确。
\ $ \ endgroup \ $
– GZ0
20 Jul 25'7:47

\ $ \ begingroup \ $
我本来要说“提高平均情况下的时间复杂度”应该只是“平均情况下的时间”，但我想我们可以说“复杂性”，并且比“复杂性类”（大- O或theta），将所有常数因子和更小的项都丢弃。我还想指出，当前三个元素不同时，提前提取可以将最佳情况下的时间缩短到O（1）。（或者使用SIMD，如果前4个元素不是全部相等，那么您只需要看一个向量即可。）对于减少解释器开销的Python特定方法，也需要+1，这对于CPython来说是巨大的。
\ $ \ endgroup \ $
– Peter Cordes
20 Jul 25'14:35

\ $ \ begingroup \ $
到目前为止，第二种解决方案的改进版本是最快的：-)
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年7月25日在21:40

#4 楼

您可以使用.most_common消除对列表理解的需要。这使代码更易于阅读。您仍然需要使用[0]，因为它将返回键和值的元组。

 def find_uniq(arr):
    return Counter(arr).most_common()[-1][0]

#5 楼

另一个仅在必要时使用O（1）来检查第一个值是否是离群值，否则使用简单的O（n）来搜索离群值。前三个中的重复值，然后搜索非重复项：

def find_uniq(arr):
    a = arr[0]
    if a not in arr[1:3]:
        return a
    for b in arr:
        if b != a:
            return b

另一个变体，首先找到一个差异对：），因为您知道Timsort：

def find_uniq(arr):
    dupe = sorted(arr[:3])[1]
    for x in arr:
        if x != dupe:
            return x

GZ0的groupby解决方案的优化版本，速度更快，并且仅占用O（1）空间：

def find_uniq(arr):
    a = arr[0]
    for b in arr:
        if b != a:
            return b if a in arr[1:3] else a

#6 楼

Counter基本上是“多集”。问题不要求对数字进行计数，因此对它们进行计数可能会产生额外的开销。这是一个可能的集合实现：

def find_uniq(arr):
    a, b = set(arr)
    return a if arr[:3].count(a) < 2 else b

这两个实现都一次通过列表，因此它们的时间复杂度为O（n）。您的列表理解，我的.count(a)和@Peilonrays的.most_common()对于大n都是微不足道的。

#7 楼

首先，请检查至少3个元素，否则未定义！
我个人将检查第一个和第二个元素：

如果不同：其中一个就是您正在找。与第三个元素比较。
如果相等：遍历所有元素直到找到它。

这似乎是最佳的解决方案：

from collections.abc import Iterable

def unique_different(iterable):
    assert isinstance(iterable, Iterable)
    assert len(iterable) > 2
    if iterable[0] != iterable[1]:
        return iterable[0] if iterable[1] == iterable[2] else iterable[1]
    else
        for element in iterable[2:]:
            if element != iterable[1]:
                return element
```

#8 楼

为什么只需要〜n时进行n/2比较？我们可以比较每对元素，直到找到不匹配的元素对，然后“短路”并返回唯一的元素。

def find_uniq(arr):
    common = arr[0]
    if common not in arr[1:3]:
        return common
    for a, b in zip(arr[1::2], arr[2::2]):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

进一步的改进是使用iter避免复制在arr语句中输入了zip。

def find_uniq(arr):
    iterator = iter(arr)
    common = next(iterator)
    if common not in arr[1:3]:
        return common
    for a, b in zip(iterator, iterator):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

\ $ \ begingroup \ $
重点是比较数。稍后将其添加到基准中。由于比较少，可能比我的类似解决方案要快，但是使用zip可能会使速度变慢。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年7月30日在11:25

\ $ \ begingroup \ $
总的来说，我的猜测是groupby和timsort解决方案将是最快的，这纯粹是因为它们都是使用时间很长的数据编写的超紧密C代码。如果您的比较足够昂贵，我的版本可能会有所帮助。因为测试数据是完全相同的对象实例（[0] * n）的数组，所以比较几乎是免费的。
\ $ \ endgroup \ $
–凯尔G
20年8月3日在15:48

\ $ \ begingroup \ $
对，我的测试数据是人为的。再说一遍，问题是:-)。（而且Codewars的原始测试用例生成器也做得差不多。）
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年8月3日在21:03

#9 楼

这是我第一次在这里发布文章，所以请让我知道我是否缺少任何约定。
这是我的解决方案，除了使用内置的sum()，不需要遍历整个数组函数：

def find_uniq(listToSearch):
    if len(listToSearch) < 3:
        return 'Cannot have one unique value unless there are at least three values.'
    
    #out of three values, minimum of two must be the same
    if listToSearch[0] == listToSearch[1]:
        commonValue = listToSearch[0]
    elif listToSearch[0] == listToSearch[2]:
        commonValue = listToSearch[0]
    elif listToSearch[1] == listToSearch[2]:
        commonValue = listToSearch[1]
    else:
        return 'Array has more than one unique value'
    
    numberOfCommonItems = len(listToSearch) - 1;
    uniqueValue = sum(listToSearch) - numberOfCommonItems * commonValue
    return uniqueValue

这些是我尝试过的测试用例：

find_uniq([ 1, 1, 1, 2, 1, 1 ])
find_uniq([ 0, 0, 0.55, 0, 0 ])
find_uniq([ 0, 0, -0.55, 0, 0 ])
find_uniq[ 1, 1.0, 1, 2, 1, 1 ])

这些是输出：

2
0.55
-0.55
2.0

此解决方案是O（ n）因为它只需要对数组的每个额外元素执行一次额外加法。除此之外，假设数据格式有效，则最多有四个if语句，一个乘法运算和一个减法运算。

\ $ \ begingroup \ $
在Codewars中失败了40％的测试用例。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20/07/26在10:37

\ $ \ begingroup \ $
我从未去过Codewars。如何找到测试用例？
\ $ \ endgroup \ $
– Mehmet
20/07/26在10:56

\ $ \ begingroup \ $
我认为您在解决问题之前看不到测试用例，但是如果将代码粘贴到那里并单击ATTEMPT，您将看到问题。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20/07/26在11:21

\ $ \ begingroup \ $
欢迎使用代码审查。我们在这里所做的是检查原始帖子中的代码，以及原始帖子的作者如何改进该代码。直到答案的最后一段，您才接近查看代码。替代解决方案在“代码审阅”中不被认为是好的答案。
\ $ \ endgroup \ $
–pacmaninbw
20/07/26在13:47

编程黑洞网