我遇到一个有趣的问题,我想知道我们是否可以解决它。
在时间复杂度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)。
s = list(s)
,如何遍历字符串'abc'
以查找key = 'a'
字典中的值?dict.get('a')
有效,但dict.get(a)
不起作用。这是我看过的2个网页,但是它们没有考虑字母顺序,也没有提供O(n)解决方案。
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)。