題目鏈接：https://leetcode.cn/problems/advantage-shuffle/

題目描述：

給定兩個(gè)大小相等的數(shù)組 nums1 和 nums2，nums1 相對(duì)于 nums2 的優(yōu)勢(shì)可以用滿足 nums1[i] > nums2[i] 的索引 i 的數(shù)目來描述。

返回 nums1 的任意排列，使其相對(duì)于 nums2 的優(yōu)勢(shì)最大化。

示例 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

解法：貪心算法

這道題的意思，總結(jié)起來就一句話，讓nums1重新排序，然后在相同索引下盡可能大于nums2的元素。也就是田忌賽馬，將兩個(gè)數(shù)組都先進(jìn)行升序排序，然后依次使用下標(biāo)i去遍歷nums1，使用left 和 right 分別表示nums2數(shù)組的最左邊下標(biāo)和最右邊下標(biāo)。

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

• 當(dāng) nums1[i] > nums2[left]，滿足題目意思，直接對(duì)號(hào)入座即可。
• 當(dāng) nums1[i] <= nums2[left]，也就是該元素已經(jīng)無法大于nums2中的剩余元素了，相當(dāng)于這把必輸，那么我們就可以去對(duì)應(yīng)nums2中的最大元素，以消耗對(duì)面的戰(zhàn)力，即讓nums1[i] 去對(duì)應(yīng) nums2[right]。

就這樣依次移動(dòng)下標(biāo) i 和 left、right直到遍歷結(jié)束。

代碼：

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;
    }
}