如何降低 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屋！