python - 2 列出 python 中的排列

Question

在做一门类(class)时它会问这个，但做了任何涵盖这样的事情我都很难过。问题如下。有答案的解释将不胜感激，以便理解。

编写一个 Python 函数，接受两个列表并计算它们是否是彼此的排列。列表可以包含整数和字符串。我们定义一个排列如下:

• 列表具有相同数量的元素

• 列表元素在两个列表中出现的次数相同

如果列表不是彼此的排列，则函数返回 False。如果它们是彼此的排列，则该函数返回一个由以下元素组成的元组:

• 出现次数最多的元素

• 该元素出现了多少次

• 出现次数最多的元素的类型

如果两个列表都是空的，则返回元组 (None, None, None)。如果不止一个元素出现次数最多，您可以返回其中任何一个。

def is_list_permutation(L1, L2):

    '''

    L1 and L2: lists containing integers and strings
    Returns False if L1 and L2 are not permutations of each other. 
            If they are permutations of each other, returns a 
            tuple of 3 items in this order: 
            the element occurring most, how many times it occurs, and its type
    '''

    # Your code here

例如，

• 如果 L1 = ['a', 'a', 'b'] 且 L2 = ['a', 'b'] 则 is_list_permutation 返回 False

• 如果 L1 = [1, 'b', 1, 'c', 'c', 1] 且 L2 = ['c', 1, 'b', 1, 1, 'c'] 那么 is_list_permutation返回 (1, 3, ) 因为出现了整数 1最多，3次，1的类型为整数(注意元组中第三个元素不是字符串)。

Answer 1

您可以使用字典 (dict) 来存储列表中项目的出现。以下是O(n) 算法。这是最好的算法

下面是你可以做的

1. 首先做一些基本的检查，比如两个列表是否有相同的长度，是否为空列表检查等

2. 使用hash map存储item to count first list的映射

3. 用第一个列表项的散列检查第二个列表

代码

def is_permutation(l1,l2):
    if len(l1) != len(l2):
        return False
    if len(l1) == 0:
        return (None,None,None)
    max_item = None
    max_count = 0
    d = dict()
    for i in l1:
        d[i] = d.get(i,0) + 1
        if d[i] > max_count:
            max_count += 1
            max_item = i
    for i in l2:
        d[i] = d.get(i,0) - 1
        if d[i] == -1:
            return False
    return (max_item,max_count,type(max_item))

print ([1,2,2,"34"],["34",2,1]),is_permutation([1,2,2,"34"],["34",2,1])
print ([],["34",2,1]),is_permutation([],["34",2,1])
print ([],[]),is_permutation([],[])
print ([1,2,2,"34",2],["34",2,2,2,1]),is_permutation([1,2,2,"34",2],["34",2,2,2,1])