LeetCode 870. 优势洗牌(贪心,二分)

题目

LeetCode 870. 优势洗牌(贪心,二分)

思路

  这道题的解题思路主要为贪心,其思想和田忌赛马类似。题目要求对于同一个索引位置,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

 

上一篇:linux ps -ef|grep 命令显示特定进程信息


下一篇:winform - FixedDialog