列表中的第 n 个重复元素

Question

我对以下解决方案的更多 pythonic 和高性能方法感兴趣。

def nthFrequent(arr,n):

    d = dict((x, arr.count(x)) for x in set(arr))

    value = sorted(d.values(), reverse=True)
    # Pick nth repeated element
    nthrepeat = value[n-1]

    for (key, val) in d.iteritems():
        if val == nthrepeat:
            return key


a=[1,2,3,4,5,6,7,92,3,2,35,9,2,43,4,9,9,9]

print nthFrequent(a,2)

上面的代码会 return 2 在 9 之后重复 3 次，即 4 次。

我正在寻找使用 lambda 的更优雅的方式，我尝试了以下方法但未获得所需的结果。

max(((item, a.count(item)) for item in set(a)), key=lambda k: k[1])[0]

上面的将得到最大重复值，即。 9.

如何获得第二个或第n个？

Answer 1

如果您正在寻找单线，以下应该可行：

return sorted(((item, a.count(item)) for item in set(a)), key=lambda k: k[1], reverse=True)[n-1][0]

虽然上面使用了更多 Python 语言特性，但我实际上更喜欢您原始代码的可读性。

附带说明一下，在您的原始代码中，您应该 return key 因为您目前正在尝试打印一个没有 return 值的函数。

如果你关心关系，正如@sberry 提到的，你可以这样做：

计数相同取最小值：

return sorted(((item, a.count(item)) for item in set(a)), 
    key=lambda k: (k[1], k[0]), reverse=True)[n-1][0]

计数相同取最大值：

return sorted(((item, a.count(item)) for item in set(a)), 
    key=lambda k: (k[1], -k[0]), reverse=True)[n-1][0]

Answer 2

collections.Counter 这非常简单。但是，请注意，如果 n 值更改为 3，此解决方案只会 return 3 或 4 之一，因为在这种情况下会出现平局。

import collections

def nthFrequent(arr,n):
    return sorted([(v, k) for k, v in collections.Counter(arr).items()], reverse=True)[n-1][1]

a = [1,2,3,4,5,6,7,92,3,2,35,9,2,43,4,9,9,9]

print nthFrequent(a,2)

还值得注意：元组列表按元组的 0 索引元素排序。因此，您可以使用带有 (count, value) 且仅 return 该值的元组。排序中不需要 lambda。

如果您真的想在没有导入的情况下执行此操作，那么即使这样实施也会更快：

def nthFrequent3(arr, n):
    d = {}
    for v in arr:
        if v not in d:
            d[v] = 0
        d[v] += 1

    return sorted([(v, k) for k, v in d.items()], reverse=True)[n-1][1]

如果您将来决定使用导入，那么也请看看 itertools。它也有一些方便的工具

def nthFrequent2(arr, n):
    for i, (value, _) in enumerate(itertools.groupby(sorted(arr))):
        if i == n - 1:
            return value

Answer 3

设N为arr的长度，这一行：

d = dict((x, arr.count(x)) for x in set(arr))

按照 N² 的顺序执行多个步骤。首先，遍历 arr 找到它的唯一元素（最坏情况是每个元素都是唯一的）。其次，对每个唯一元素，再次遍历整个列表，统计该元素出现了多少次。你的一线解也是按N².

的顺序

这是很多不必要的重复步骤。您只需要查看 arr 的每个元素一次。只需一步，您就可以：

检查你是否已经看过这个元素
增加该元素的计数器

像这样：

counter = {}

for x in arr:
    if x not in counter:
        counter[x] = 0
    counter[x] += 1

pairs = sorted(counter.iteritems(), key=lambda pair: pair[1], reverse=True)

key, count = pairs[n]
return key

在最坏的情况下，每个元素都是唯一的，由于排序，此代码会按 N*log(N) 的顺序执行多个步骤。（通过 arr 的顺序为 N，因为 Python 中的 dict 查找在摊销 1 的顺序。)

列表中的第 n 个重复元素

nth repeated element in a list

python

list

repeat