找出出现奇数次的字母

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) 以上。

我的问题：

任何人都可以就 O(n) 解决方案提供一些建议吗？
如果我不想使用 s = list(s)，如何迭代字符串 'abc' 以在字典中查找 key = 'a' 的值？ dict.get('a') 有效，但 dict.get(a) 无效。

来源

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

find even time number, stack overflow
find odd time number, geeks for geeks

Answer 1

Python 3.7 以上的字典键输入顺序。 collection.OrderedDict 用于较低的 python 版本。

检查你的单词，如果不在则添加字母做字典，否则从字典中删除键。

解决方案是 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)，因为您输入的每个字母恰好触摸一次 - 查找字典的复杂度为 O(1)。

按键有一些开销 adding/deleting。如果这让您感到困扰，请改用计数器并过滤 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]

Answer 4

我从零开始的解决方案

其实是利用了Python 3.6中的dict是key-ordered的特性

def odd_one_out(s):

    hash_map = {}
    # reverse the original string to capture the last occurance
    s = list(reversed(s))
    res = []
    for i in range(len(s)):
        if hash_map.get(s[i]):
            hash_map[s[i]] += 1

        else:
            hash_map[s[i]] = 1
    for k,v in hash_map.items():
        if v % 2 != 0:
            res.append(k)

    return res[::-1]

疯狂的超短解

#from user FArekkusu on Codewars
from collections import Counter

def find_odd(s):
    d = Counter(reversed(s))
    return [x for x in d if d[x] % 2][::-1]

Answer 5

使用集合中的计数器将为您提供一个复杂度为 O(n) 的解决方案。由于 Counter 对象是一个字典（保留出现顺序），您的结果可以简单地作为计数过滤器：

from collections import Counter

text = 'Hello World'
oddLetters = [ char for char,count in Counter(text).items() if count&1 ]
print(oddLetters) # ['H', 'e', 'l', ' ', 'W', 'r', 'd']

找出出现奇数次的字母

Find the Letters Occurring Odd Number of Times

python

algorithm

lookup

dictionary

背景

我的尝试

我的问题：

来源

我从零开始的解决方案

疯狂的超短解