查找出现奇数次的字母

Question

我遇到了一个有趣的问题，我想知道我们是否能解决它

背景

在时间复杂度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'来查找dict中key = 'a'的值dict.get('a')有效，但dict.get(a)无效。

来源

这里有两个网页，我看了，但他们没有考虑到信的顺序，并没有提供O（n）的解决方案

1. find even time number, stack overflow
2. find odd time number, geeks for geeks

Answer 1

Python3.7以上版本具有按顺序输入的字典键。对于较低的python版本，请使用collection.OrderedDict

通读单词，若不在，则添加字母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）

Answer 2

下面是一个尝试（键在python 3.6 dict中排序）：

from collections import defaultdict

def find_odd(s):
    counter = defaultdict(int)
    for x in s:
        counter[x] += 1
    return [l for l, c in counter.items() if c%2 != 0]

该算法的复杂度小于2n，即O（n）

示例

>>> s = "hello world"
>>> find_odd(s)
['h', 'e', 'l', ' ', 'w', 'r', 'd']

Answer 3

您可以使用哈希映射来存储字符出现的索引，并在该索引已有值时进行切换

然后，您只需再次迭代字符串，并仅保留哈希映射中索引处出现的字母：

from collections import defaultdict

def findodd(s):
    hash_map = defaultdict(int)
    for i, c in enumerate(s):
        hash_map[c] = 0 if hash_map[c] else i+1
    return [c for i, c in enumerate(s) if hash_map[c] == i+1]