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.

Example 1:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
Output: [24,32,8,12]

Constraints:

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

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

题目大意：给两个数组，可任意改变nums1中的元素顺序，要求nums1比对应下标的nums2中元素大的个数尽量多

题目分析：比较明显的贪心题，容易发现对nums2中的数字，在nums1中找比其大的最小的数放在与其相应的位置是最优的（证明：假设nums1[idx] = a, nums1[idx2] = c, nums2[idx] = b，c > a > b，如果将c交换到idx处，若之后存在nums2[idx3] = d且c > d > a，则会损失一对符合条件的数对），具体做法是对nums1和nums2分别从小到大排序，nums2在排序时需记录原始下标，然后按上面的结论用双指针遍历即可，如果对当前的nums2，不大于它的nums1均可作为自由数，放置在不能形成合法数对的任何位置上

84ms，时间击败72.2%

class Solution {
    
    class Item {
        int val, idx;
        Item(int v, int i) {
            this.val = v;
            this.idx = i;
        }
    }
    
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Item[] items2 = new Item[n];
        for (int i = 0; i < n; i++) {
            items2[i] = new Item(nums2[i], i);
        }    
        Arrays.sort(items2, (i1, i2) -> i1.val - i2.val);
        Arrays.sort(nums1);

        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        int[] rest = new int[n];
        int cnt = 0, i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && nums1[i] <= items2[j].val) {
                rest[cnt++] = nums1[i++];
            }
            if (i == n) {
                break;
            }
            ans[items2[j++].idx] = nums1[i++];
        }
        for (i = 0; i < n; i++) {
            if (ans[i] == -1) {
                ans[i] = rest[--cnt];
            }
        }
        return ans;
    }
}

还有一种更简洁的方法，在处理自由数时，上面是先进行记录再赋值给ans，其实没有很好利用到两个数组都有序的特征，不妨从大到小遍历，对当前nums1的值，若大于nums2则记入答案，否则说明不可能找到更大的nums1比当前nums2大了，因为是从大到小遍历的，此时直接拿nums1中最小的数字来填即可

class Solution {
    
    class Item {
        int val, idx;
        Item(int v, int i) {
            this.val = v;
            this.idx = i;
        }
    }

    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Item[] items2 = new Item[n];
        for (int i = 0; i < n; i++) {
            items2[i] = new Item(nums2[i], i);
        }    
        Arrays.sort(items2, (i1, i2) -> i1.val - i2.val);
        Arrays.sort(nums1);

        int[] ans = new int[n];
        int l = 0, r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[items2[i].idx] = nums1[r] > items2[i].val ? nums1[r--] : nums1[l++];
        }
        return ans;
    }
}