题目

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：
输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

示例 2：
输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

提示：
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9

思路

1. 求A的全排列，并保留计算与其优势值(O(n!))
2. 从A的某种状态开始，不断通过调换每个位置的值来使得A的优势值增加，直到无法改变A(O(n!))
3. 将B与A都按照从小到大排序，这样使得每个数组A的数的位置都能是刚好大于B对应的那一个，最后再根据这个映射还原回原来的位置(最坏O(n^2))，对于那些没有在A中找到大于B最小未匹配数字的，最后只需要遍历完成后在未分配的部分随便给一个数字

• 最后这个思路使用贪心来寻找A中恰好比B大的那个数字

实现上的细节和坑

1. 需要注意的是nums2里可能出现字符重复，所以可以使用字典 key(int):value(list)来进行pop弹出对应的映射值
2. 在最后输出循环的时候，可能存在num2_dict.get(nums2[i])中已经是空的了，说明其映射已经被取完，应该判断一下再去unassigned的数中去取

Pytnon实现

class Solution:
    def advantageCount(self, nums1: list, nums2: list) -> list:
        # 给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
        # 返回 A 的任意排列，使其相对于 B 的优势最大化。
        # 1. 求A的全排列，并保留计算与其优势值(O(n!))
        # 2. 从A的某种状态开始，不断通过调换每个位置的值来使得A的优势值增加，直到无法改变A(O(n!))
        # 3. 将B与A都按照从小到大排序，这样通过构建映射，使得每个数组A的数的位置都能是刚好大于B对应的那一个，最后再根据这个映射还原回原来的位置(最坏O(n^2))
        temp_nums1=sorted(nums1)
        temp_nums2=sorted(nums2)
        # 需要注意的是nums2里可能出现字符重复，所以可以使用字典 key(int):value(list)
        num2_dict={}

        assigned = [0 for i in range(len(nums1))]  # 0表示temp_nums1的数字还没有被分配，1代表被分配了

        for num in temp_nums2:
            for index in range(len(temp_nums1)):
                if (temp_nums1[index] > num and assigned[index] == 0):
                    # 找到了第一个大于 num 的数字
                    if(num2_dict.get(num)==None):
                        num2_dict[num]=[]
                    num2_dict[num].append(temp_nums1[index])
                    assigned[index]=1
                    break

        # 没有在A中找到大于该数字的，最后只需要遍历完成后在未分配的部分随便给一个数字
        unassigned=[]
        for i in range(len(assigned)):
            if(assigned[i]==0):
                unassigned.append(temp_nums1[i])

        result=[]
        for i in range(len(nums2)):
            if(num2_dict.get(nums2[i])!=None):
                temp=num2_dict.get(nums2[i])
                if(len(temp)>0):
                    result.append(temp.pop(0))
                else:
                    result.append(unassigned.pop(0))
            else:
                result.append(unassigned.pop(0))
        return result


if __name__=="__main__":
    s=Solution()
    A = [2,0,4,1,2]
    B = [1,3,0,0,2]
    # 输出：[2, 11, 7, 15]
    C=s.advantageCount(A,B)
    print(C)

优化

看了官方的代码后，发现有一些细节上可以优化

1. 第一个点是 由于temp_nums2是排好序的，所以可以通过记录下标的方法，去除外层对temp_nums2的循环，同时内部就不需要break了
2. 第二个点是，如果 num1 没有大于对应最小的num2，可以加入到unassigned中去，因为其一定是未分配的了，不需要单独的进行循环来实现unassigned的构建

class Solution:
    def advantageCount(self, nums1: list, nums2: list) -> list:
        # 给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
        # 返回 A 的任意排列，使其相对于 B 的优势最大化。
        # 1. 求A的全排列，并保留计算与其优势值(O(n!))
        # 2. 从A的某种状态开始，不断通过调换每个位置的值来使得A的优势值增加，直到无法改变A(O(n!))
        # 3. 将B与A都按照从小到大排序，这样使得每个数组A的数的位置都能是刚好大于B对应的那一个，最后再根据这个映射还原回原来的位置(最坏O(n^2))
        temp_nums1=sorted(nums1)
        temp_nums2=sorted(nums2)
        # 需要注意的是nums2里可能出现字符重复，所以可以使用字典 key(int):value(list)
        num2_dict={}

        assigned = [0 for i in range(len(nums1))]  # 0表示temp_nums1的数字还没有被分配，1代表被分配了

        # for num in temp_nums2:
        #     for index in range(len(temp_nums1)):
        #         if (temp_nums1[index] > num and assigned[index] == 0):
        #             # 找到了第一个大于 num 的数字
        #             if(num2_dict.get(num)==None):
        #                 num2_dict[num]=[]
        #             num2_dict[num].append(temp_nums1[index])
        #             assigned[index]=1
        #             break

        # 由于temp_nums2是排好序的，所以可以通过记录下标的方法，减少外层的循环
        # 同时，如果 num1 没有大于对应最小的num2，可以加入到unassigned中去
        index_2=0
        unassigned = []
        # for num in temp_nums2:
        for index in range(len(temp_nums1)):
            if (temp_nums1[index] > temp_nums2[index_2] and assigned[index] == 0):
                # 找到了第一个大于 num 的数字
                if (num2_dict.get(temp_nums2[index_2]) == None):
                    num2_dict[temp_nums2[index_2]] = []
                num2_dict[temp_nums2[index_2]].append(temp_nums1[index])
                assigned[index] = 1
                index_2 += 1
            else:
                unassigned.append(temp_nums1[index])


        # # 没有在A中找到大于该数字的，最后只需要遍历完成后在未分配的部分随便给一个数字
        # unassigned=[]
        # for i in range(len(assigned)):
        #     if(assigned[i]==0):
        #         unassigned.append(temp_nums1[i])

        result=[]
        for i in range(len(nums2)):
            if(num2_dict.get(nums2[i])!=None):
                temp=num2_dict.get(nums2[i])
                if(len(temp)>0):
                    result.append(temp.pop(0))
                else:
                    result.append(unassigned.pop(0))
            else:
                result.append(unassigned.pop(0))
        return result


if __name__=="__main__":
    s=Solution()
    A = [12,24,8,32]
    B=[13,25,32,11]
    # 输出：[2, 11, 7, 15]
    C=s.advantageCount(A,B)
    print(C)

【LeetCode&python】870. 优势洗牌

原文：https://www.cnblogs.com/heyjjjjj/p/15000303.html