该文章创建(更新)于03/7/2022，请注意文章的时效性！

You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].

Return any permutation of nums1 that maximizes its advantage with respect to nums2.

• https://leetcode.com/problems/advantage-shuffle/

Solution

Use The Worst to Defeat The Best.

• The only thing I can't understand is that the Except answer [2,0,4,1,2] when the nums2 is [1,3,0,0,2],and submit code answer [2, 4, 1, 2, 0] for is this is all right.It seems it just ok for the right number of answer.

Code

• submit code

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:

        nums1.sort()

        result = [0 for i in range(len(nums1))]

        left = 0
        right = len(nums1) - 1

        # The Most Important 
        # Be caution the same vaule in nums2 
        sorted_b = sorted(enumerate(nums2), key=lambda x: (x[1], x[0]),
                          reverse=True)  # descending order with original index

        for index,value in sorted_b:
            if nums1[right] > value:
                result[index] = nums1[right]
                right -= 1
            else:
                result[index] = nums1[left]
                left += 1

        return result

• full code

import time


class Solution:
    def advantageCount(self, nums1,nums2):

        maxpq = nums2.copy()

        # maxpq.sort(reverse=True)
        maxpq.sort()
        print("nums2:\t" + str(nums2))

        print("maxpq:\t" + str(maxpq) )

        nums1.sort()

        print("nums1:\t" + str(nums1))

        result = [-1 for i in range(len(nums1))]

        left = 0
        right = len(nums1) - 1

        print("######################\n")

        # 有重复值时不正确
        # while len(maxpq) > 0:
        #     # 这里的i是个问题，当有重复值时取得时第一个索引值
        #     i = nums2.index(max(maxpq))
        #     print("left:\t" + str(left) + " right:\t" + str(right) + " i:\t" + str(i) + " nums1[right]:\t" + str(nums1[right]) )
        #     time.sleep(1)
        #     if(nums1[right] > max(maxpq)):
        #         result[i] = nums1[right]
        #         right -= 1
        #     elif left < len(nums1) - 1:
        #         result[i] = nums1[left]
        #         left += 1
        #     maxpq.pop()
        #     print("result:\t" + str(result))
        #     print("maxpq:\t" + str(maxpq))
        #     print("")
        sorted_b = sorted(enumerate(nums2), key=lambda x: (x[1], x[0]),
                          reverse=True)  # descending order with original index

        for index,value in sorted_b:
            if nums1[right] > value:
                result[index] = nums1[right]
                right -= 1
            else:
                result[index] = nums1[left]
                left += 1

        return result

# maxpq是为了不打乱nums2的顺序，同时又能查到某个值在其中的位置用于对应result需要填写的位置


S = Solution()

nums1 = [2,7,11,15]
nums2 = [1,10,4,11]
# [2,11,7,15]

nums1 = [12,24,8,32]
nums2 = [13,25,32,11]
#[24,32,8,12]

nums1 = [2,0,4,1,2]
nums2 = [1,3,0,0,2]
 # [2,0,2,1,4]
 ###########################################
 # 重复的元素,的索引值在nums中是一样的导致出错
 ###########################################

print(S.advantageCount(nums1,nums2))

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin