题目分析

本题很明显是一个贪心题目，类似于一个田忌赛马的思维逻辑，对于num2中的数x，我们只需要在num1中找到一个比x大的最小的数即可，如果无法找到比x大的数，那么就将num1中最小的数放在该位置。类似于让num2的上等马对num1的下等马。

贪心

因为本题要对每一个num2中的元素都在num1中寻找比它大的最小的数。因此可以对num1和num2进行排序。

以示例2说明，num1排序后为[8, 12, 24, 32]，num2排序后为[11, 13, 25, 32]。

对于排序后num1的元素和排序后num2的元素进行比较，如果大于num2，则放在num2对应的位置，如果小于等于num2，则放在num2最后。

8小于11，因此8放在num2最后，对应32，因为num2的11还没有找到更大的元素，因此不移动。
12大于11，因此12放在11的位置，对应11，因为num2的11找到更大的元素，向后移动。
24大于13，因此24放在13的位置，对应13，因为num2的13找到更大的元素，向后移动。
32大于25，因此32放在25的位置，对应25，因为num2的25找到更大的元素，向后移动。

如果仅需要找到大于的次数(或者说符合条件的元素对数)，则本题就简单了，只需要看num2移动多少步即可。

这里输出的是num1的排列结果，因此还要复原num2对应的位置。因此不能直接对num2进行排序，会打乱元素原始位置。

新建一个sort2数组，表示元素下标，对sort2进行排序，让对应元素小的下标放在前面。

使用left和right双指针表示当前比较sort2中的哪一个元素，num1中的元素大于sort2中对应的元素，则放在left处，left++；否则放在right处，right–。给res赋值时，要还原nums2对应的位置，即sort2对应的下标。

算法的**时间复杂度为O(nlog(n))，空间复杂度为O(n)**。

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Integer[] sort2 = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(nums1);
        Arrays.sort(sort2, Comparator.comparingInt(o -> nums2[o]));
        int left = 0;
        int right = n - 1;
        int[] res = new int[n];
        for (int x : nums1) {
            if (x > nums2[sort2[left]]) {
                res[sort2[left++]] = x;
            } else {
                res[sort2[right--]] = x;
            }
        }
        return res;
    }
}

刷题总结

本题的难点是想到田忌赛马的逻辑，如果能想到这一层，剩下的就是如何将下标进行还原。