力扣-870.优势洗牌

题目描述

思路及实现

根据题目我们很容易想到用贪心解决问题。即每次取nums1中最小的数字跟nums2中的比较。可以将nums1按升序排序，用另一个数组reslut保存结果。
最开始无脑写的：

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        result: List[int] = []
        for num2 in nums2:
            for i, num1 in enumerate(nums1):
                if num1 > num2:
                    nums1.remove(num1)
                    result.append(num1)
                    break
                elif i == len(nums1) - 1:  # 没有大于数组2当前数字的数字了
                    result.append(nums1.pop(0))
        return result

超时，好的，我就知道（怕不怕我10^5长度的数组）。重新想过后，确实有更好的方法，原理不变，也是贪心，但是对两个数组都进行排序，并“浪费”点空间，创建一些辅助数组。
我们对数组1进行遍历，对nums2则是利用一下双指针。当nums1的数大于nums2的数时，由于我们已经排过序，那么此时肯定满足优势最大化，因为nums1之后的数都会比当前数大了，所以直接进行配对就行。
如果小于的话，那这个数也小于nums2之后的数，所以就把这个数丢给nums2中最大的数，也就是尾指针指向的数。
其实难点在于怎么保持原来的顺序输出，也就是下标问题。由于sort()函数接受一个key参数，而这个参数会将接收到的数据用于排序的关键，所以可以利用这点来排序下标数组，以保证最后的输出。
由于我们的数是一一对应的，所以不必担心重复访问，也就是说，我们可以直接对nums2数组进行修改，并返回它。

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        len2 = len(nums2)
        index2 = list(range(len2))
        index2.sort(key=lambda x: nums2[x])
        nums1.sort()
        head = 0
        tail = len2 - 1
        for num in nums1:  # 遍历数组1
            if num > nums2[index2[head]]:
                nums2[index2[head]] = num
                head += 1
            else:
                nums2[index2[tail]] = num
                tail -= 1
        return nums2

---

希望本文章能够帮到您~