温馨提示:本文翻译自stackoverflow.com,查看原文请点击:python - Find the Letters Occurring Odd Number of Times
algorithm dictionary lookup python

python - 查找出现奇数次的字母

发布于 2020-04-12 12:02:48

我遇到一个有趣的问题,我想知道我们是否可以解决它。

背景

在时间复杂度O(n)中,我们可以找到出现奇数次的字母吗,输出包含字母的列表,并保持字母顺序与原始字符串一致

如果有多个选项可供选择,则以最后一次出现作为未配对的字符。

这是一个例子:

# note we should keep the order of letters
findodd('Hello World')   ==  ["H", "e", " ", "W", "r", "l", "d"] # it is good
findodd('Hello World')   ==  ["H", "l", " ", "W", "r", "e", "d"] # it is wrong

我的尝试

def findodd(s):
    hash_map = {}

    # This step is a bit strange. I will show an example:
    # If I have a string 'abc', I will convert string to list = ['a','b','c']. 
    # Just because we can not use dict.get(a) to lookup dict. However, dict.get('a') works well.
    s = list(s)

    res = []
    for i in range(len(s)):
        if hash_map.get(s[i]) == 1:
            hash_map[s[i]] = 0
            res.remove(s[i])
        else:
            hash_map[s[i]] = 1
            res.append(s[i])

    return res
findodd('Hello World')

出:

["H", "e", " ", "W", "r", "l", "d"] 

但是,由于我使用list.remove,所以我的解决方案中的时间复杂度高于O(n)。

我的问题:

  1. 谁能提供有关O(n)解决方案的建议?
  2. 如果我不想使用s = list(s),如何遍历字符串'abc'以查找key = 'a' 字典中的值dict.get('a')有效,但dict.get(a)不起作用。

资源

这是我看过的2个网页,但是它们没有考虑字母顺序,也没有提供O(n)解决方案。

  1. 查找偶数时间,堆栈溢出
  2. 查找奇数时间数字,极客

查看更多

提问者
Travis
被浏览
23
Patrick Artner 2020-02-02 23:31

Python 3.7 up已命令字典键输入。collection.OrderedDict用于较低的python版本。

仔细检查您的单词,如果不在,则添加字母do dict,否则从dict中删除键。

解决方案是dict.keys()集合:

t = "Hello World"

d = {}
for c in t:
    if c in d:       # even time occurences: delete key
        del d[c]
    else:
        d[c] = None  # odd time occurence: add key

print(d.keys()) 

输出:

dict_keys(['H', 'e', ' ', 'W', 'r', 'l', 'd'])

之所以为O(n),是因为您只需一次触摸输入中的每个字母-查找dict就是O(1)。

密钥添加/删除会产生一些开销。如果那让您感到困扰,请改用计数器,并过滤那些奇怪的key()集合-这将使其变为O(2 * n)-2不变,因此仍为O(n)。