题目

思路

  这道题的解题思路主要为贪心，其思想和田忌赛马类似。题目要求对于同一个索引位置，A[i]>B[i]的索引数目。为了让“资源”利用率最大化，对于B位置某个索引处的元素，对应调出的A数组中的元素应该是刚刚好大于它，也就是A数组中大于该元素的第一个数。如果不存在这样的数（或者有合适的数但之前已被占用）则将当前A数组中可用的最小值分给它，减少资源的损失。为了更快查找到该元素，需要先对A数组进行排序。之后遍历B数组。对于B数组中的而每个元素,在A数组中二分查找第一个大于当前元素的数并加入答案。如果找不到则将当前的最小数加入答案。整个过程中A数组需要对应弹出已被选择的元素。

代码

 

class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        n=len(A)
        #tempb=copy.deepcopy(B)
        A.sort()
       # tempb.sort()
        la=0
        ans=[]
        pair={}
        vis={}
        for temp in B:
            l=0
            r=len(A)-1
            while l<=r:
                mid=l+r>>1
                #
                if A[mid]<=temp:
                    l=mid+1
                else:
                    r=mid-1
           # print(l,r,mid)
            if l>=len(A):
                if pair.get()
                ans.append(A.pop(0))
            else:
                ans.append(A[l])
                A.pop(l)
            #print(ans)
        return ans