870. 优势洗牌（难度：中等）

题目链接：https://leetcode.cn/problems/advantage-shuffle/

题目描述：

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

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

示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

• 1 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 109

解法：贪心算法

这道题的意思，总结起来就一句话，让nums1重新排序，然后在相同索引下尽可能大于nums2的元素。也就是田忌赛马，将两个数组都先进行升序排序，然后依次使用下标i去遍历nums1，使用left 和 right 分别表示nums2数组的最左边下标和最右边下标。

使用nums1最小的元素去和nums2最小元素比较，

• 当 nums1[i] > nums2[left]，满足题目意思，直接对号入座即可。
• 当 nums1[i] <= nums2[left]，也就是该元素已经无法大于nums2中的剩余元素了，相当于这把必输，那么我们就可以去对应nums2中的最大元素，以消耗对面的战力，即让nums1[i] 去对应 nums2[right]。

就这样依次移动下标 i 和 left、right直到遍历结束。

代码：

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums2.length;
        Integer[] index1 = new Integer[n];
        Integer[] index2 = new Integer[n];
        for (int i = 0; i < n; i++) {
            index1[i] = i;
            index2[i] = i;
        }
        Arrays.sort(index1, Comparator.comparingInt(a -> nums1[a]));
        Arrays.sort(index2, Comparator.comparingInt(a -> nums2[a]));

        int[] ans = new int[n];
        int left = 0, reight = n - 1;
        for (int i = 0; i < n; i++) {
            if (nums1[index1[i]] > nums2[index2[left]]) {
                ans[index2[left]] = nums1[index1[i]];
                left++;
            } else {
                ans[index2[reight]] = nums1[index1[i]];
                reight--;
            }
        }
        return ans;
    }
}