高效查找字符串中的重复字符

Question

我知道这段代码的效率不是最好的，尤其是当输入数据非常大的时候。我也知道有办法可以改进这个算法，让它不仅仅处理字符串中的重复字符（毕竟可供搜索的字符数量是有限的）。

有没有什么方法可以提高这里的效率呢？

我试着用字典来实现，但函数一直返回'none'，所以我换成了列表，结果就正常了。

提前感谢任何能帮我解决问题的人！

def find_repeater(string):
    my_list = []
    my_list.append(string[0])

    for i in range (1, len(string)):

        if string[i] in my_list:
            print 'repetition found'
            return (string[i])

        else:
            my_list.append(string[i])

print find_repeater('abca')  

现在用字典来试试……（它一直在控制台打印'none'）

def find_repeater(string):
    my_dict = {}
    my_dict[0] = string[0]

    for i in range (1, len(string)):

        if string[i] in my_dict:
            print 'repetition found'
            return string[i]

        else:
            my_dict[i] = string[i]

print find_repeater('abca')  

Answer 1

这个应该可以正常运行。

def return_dupe(string):
    d = {}
    [d.update({k:2}) if k in d else d.update({k:1}) for k in string]
    return [key for key in d if d[key] > 1]

Answer 2

这里有一个使用字典的例子：

def find_repeater(string):
    my_list = {}
    my_list[string[0]] = 1
    for i in range (1, len(string)):
        if string[i] in my_list.keys():
            print 'repetition found'
            return (string[i])
        else:
            my_list[string[i]] = 1
print find_repeater('abca')  

不过，我个人更倾向于在这里使用集合：

def find_repeater(string):
    my_list = set()
    my_list.add(string[0])
    for i in range (1, len(string)):
        if string[i] in my_list:
            print 'repetition found'
            return (string[i])
        else:
            my_list.add(string[i])
print find_repeater('abca')  

Answer 3

在编程中，有时候我们需要处理一些数据，比如从一个地方获取数据，然后在另一个地方使用这些数据。这个过程就像是把水从一个水桶倒到另一个水桶里。我们需要确保水不会洒出来，也就是要保证数据的完整性。

有些时候，我们会用到一些工具或者库来帮助我们更方便地处理这些数据。这就像是用一个漏斗来倒水，可以让水流得更顺畅，不容易洒出来。

在这个过程中，我们还需要注意数据的格式。就像水有不同的温度和颜色一样，数据也有不同的类型，比如数字、文字或者图片。我们需要确保在使用这些数据的时候，它们的格式是正确的，这样才能顺利地进行后续的操作。

总之，处理数据就像是一个精细的操作，需要我们小心翼翼地进行，确保每一步都能顺利完成。

def find_repeater(mystr):
    seen = set()  # O(1) lookups
    for char in mystr:
        if char not in seen:
            seen.add(char)
        else:
            print('repetition found')
            return char

Answer 4

你可以使用 collections 这个工具来找出重复的字符：

import collections

freq = collections.Counter("abcda")
for k in freq:
    if freq[k] > 1:
        print k # prints "a"
        break

如果你只是想知道是否有重复的字符（而不需要找出具体哪些字符重复）：

letters = list("abcda")
no_rep = set(letters)
print len(letters) > len(no_rep) # prints 'True' when there are repeating characters

Answer 5

因为这是一个关于性能的问题，我们来做一些时间测试：

def test_set(xs):
    seen = set()  # O(1) lookups
    for x in xs:
        if x not in seen:
            seen.add(x)
        else:
            return x

import collections

def test_counter(xs):
    freq = collections.Counter(xs)
    for k in freq:
        if freq[k] > 1:
            return k

def test_dict(xs):
    d = {}
    for x in xs:
        if x in d:
            return x
        d[x] = 1

def test_sort(xs):
    ys = sorted(xs)

    for n in range(1, len(xs)):
        if ys[n] == ys[n-1]:
            return ys[n]

##

import sys, timeit
print (sys.version + "\n")
xs = list(range(10000)) + [999]
fns = [p for name, p in globals().items() if name.startswith('test')]
for fn in fns:
    assert fn(xs) == 999
    print ('%50s %.5f' % (fn, timeit.timeit(lambda: fn(xs), number=100)))

我在测试一个整数列表，而不是字符串（因为用字符串的话，循环次数最多只能到256次）。在我的机器上，结果是这样的：

3.2.3 (v3.2.3:3d0686d90f55, Apr 10 2012, 11:25:50) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)]

                <function test_set at 0x1020f7380> 0.19265
               <function test_dict at 0x1020f7490> 0.12725
               <function test_sort at 0x1020f7518> 0.04683
            <function test_counter at 0x1020f7408> 0.92485

所以排序方法看起来是表现最好的。我想这是因为它没有浪费时间去创建哈希表和分配字典或集合的结构。而且，如果你不在乎原始列表被改变的话，可以用 xs.sort() 代替 ys = sorted(xs)，这样就不会占用额外的内存。

另一方面，如果输入的重复项更可能出现在开头（比如 xs = 'abcdef' * 10000），那么 set 方法会表现得最好，因为它和 sort 或 Counter 不同，一旦找到重复项就会立即返回，不需要先处理整个列表。如果你需要的是第一个重复的元素，而不仅仅是其中一个，也应该使用 set。

Counter 是一个很不错的工具，但它并不是为了性能而设计的，所以如果你真的需要处理“巨大的输入”，就选择集合（如果它们能放进内存的话），或者如果不能，就用归并排序。