Python 比较两个排序列表并计算有多少元素相同的算法

Question

我必须设计一个算法来比较两个相同长度的排序列表和return它们之间的共同值的数量。

所以如果我有两个列表 a = [2, 9, 15, 27, 36, 40] 和 b = [9, 11, 15, 23, 36, 44]，算法应该 return 3 作为 9、15 和 36 的值出现在两个列表中。

我知道使用集合可能更容易，但由于我正在尝试学习数据结构和算法，所以我更愿意学习时间更长（更难）。

我当前的代码使用了目前无法正常工作的任何数组合并算法，因为我仍然对 r1 和 r2 感到困惑，虽然我认为它们将是数组中最正确的元素，但我不知道不知道如何得到它。例如。 r1 = 40（来自列表 a）和 r2 = 44（来自列表 b）？

global a
a = [2, 9, 15, 27, 36, 40]

global b
b = [9, 11, 15, 23, 36, 44]

global c
c = []

def merge (a1, a, r1, a2, b, r2, c, list3):
    i = a
    j = b
    k = c
    r1 = 
    r2 = 
    while i <= r1 and j <= r2:
        if a1[i]<=a2[j]:
            a3[k] = a1[i]
            i += 1
        elif a3[k] >= a2[j]:
            j += 1
            k += 1
    while i <= r1:  
        a3[k] = a1[i]
        i += 1
        k += 1 
    while j <= r2:  
        a3[k] = a2[j]
        j += 1
        k += 1

感谢您的帮助和反馈。

Answer 1

r1 和 r2 只是两个列表的长度。
对 2 个列表进行简单合并并不像您的示例那么复杂，这里是一个简化的合并：

def merge(a1, a2):
    r1, r2 = len(a1), len(a2)
    a3 = []
    i = j = 0

    while i < r1 and j < r2:
        if a1[i] < a2[j]:
            a3.append(a1[i])
            i += 1
        else:
            a3.append(a2[j])
            j += 1

    while i < r1:
        a3.append(a1[i])
        i += 1
    while j < r2:
        a3.append(a2[j])
        j += 1

    return a3

In []:
a = [2, 9, 15, 27, 36, 40]
b = [9, 11, 15, 23, 36, 44]
merge(a, b)

Out[]:
[2, 9, 9, 11, 15, 15, 23, 27, 36, 36, 40, 44]

重复计数比这更简单，因为您不需要构建新列表，但这应该为您提供计数的基础，而且只是 O(n)。

Answer 2

好的，如果我没看错你的问题，你想在两个长度相等的排序列表中找到公共元素，return 公共元素的数量。我对这里使用 merge 有点困惑。

无论如何，如果这是您希望算法执行的操作。由于它已经排序，我们可以简单地遍历两个列表并在线性时间内找到公共元素。

算法：

设i和j为a1和a2的索引分别初始化为0
如果a1[i] < a2[j]我们知道a1[i]在a2中不存在因为i和j指向各自数组中的最小元素.所以我们向前移动i。
与a2[j] < a1[i]相同。
如果 a1[i] == a2[j] 则我们找到了一个公共元素，我们将 i 和 j 都推进 1 并继续直到任一数组的末尾。

代码

def find_common(a1, a2):
    list_len = len(a1)
    a3 = []
    i = j = 0
    while i < list_len and j < list_len:
        if a1[i] < a2[j]:
            i += 1
        elif a2[j] < a1[i]:
            j += 1
        else:
            a3.append(a1[i])    
            i +=1
            j +=1
    return a3

a = [2, 9, 15, 27, 36, 40]
b = [9, 11, 15, 23, 36, 44]
print(find_common(a, b))

Answer 3

使用哈希 table 你可以在线性时间内解决这个问题。

您可以使用 python 字典将一个列表存储在散列 table 中，其中键是元素（在本例中是整数），值是出现的次数元素。运行时间：O(n)

然后遍历另一个列表并对每个元素进行散列 table 查找。保留一个变量来计算公共值。运行时间：O(n).

为避免计算重复项，在迭代时检查前一个元素是否相同，如果相同则移至下一个元素。您将需要一个额外的变量来跟踪前一个元素。

Python 比较两个排序列表并计算有多少元素相同的算法

Python algorithm to compare two sorted lists and count how many elements are the same

python

algorithm

array-merge

python-3.x