如何降低 Python 中这段代码片段的时间复杂度? [英] How do I reduce the time complexity of this code snippet in Python?
问题描述
我在这里有一个 compare
函数,它比较 2 个 4 位数字(非重复数字)并给出 x
(n1
和 n2
并在同一位置)和 y
(n1
和 n2
,但在不同的位置).我所做的是使用 for
循环将数字存储为 results
字典的键,并将相应位置存储为 results
的值> 字典.然后,我使用另一个 for
循环遍历字典,得到 x
和 y
.有没有办法降低这个函数的时间复杂度?
I have a compare
function here which compares 2 4-digit numbers (non-repeating digits) and gives x
(no. of digits in both n1
and n2
and in the same position), and y
(no. of digits in both n1
and n2
, but in different positions). What I do is I use a for
loop to store the digit as the key of the results
dictionary and the corresponding position as the value of the results
dictionary. Then, I use another for
loop to iterate through the dictionary to give me x
and y
. Is there any way of reducing the time complexity of this function?
def compare(n1, n2):
x, y = 0, 0
result = {}
s1, s2 = str(n1), str(n2)
for i in range(0, 4):
result[s1[i]] = i
for i in range(0, 4):
if s2[i] in result:
if result[s2[i]] == i:
x += 1
else:
y += 1
推荐答案
@DeGo 说没有比 o(n) 更好的了.但是,您可以改进代码,因为您正在做绝对没有必要的事情.我将代码重写为
@DeGo said you can't go better than o(n). However, you code can be improved since you are doing things that are absolutely not necessary. I would rewrite the code as
from collections import Counter
def compare(n1, n2):
digits_at_same_position, digits_at_diff_position = 0, 0
s1, s2 = str(n1), str(n2)
l1 = list(map(lambda x, y: x == y, s1, s2))
digits_at_same_position = sum(l1)
l2 = list((Counter(s1) & Counter(s2)).elements())
digits_at_diff_position = len(l2) - digits_at_same_position
return digits_at_same_position, digits_at_diff_position
print(compare(1234, 2435))
效率等级是一样的.但是,此代码会比您的更快.
The class of efficiency is the same. However, this code will be faster than yours.
输出:
>> (1, 2)
这篇关于如何降低 Python 中这段代码片段的时间复杂度?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!