870. 优势洗牌

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

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

超时代码

一开始的思路：因为nums2的顺序不能改变，那就遍历nums2数组，为每个数尽可能找到一个nums1中比它大的数，设计一个数组用于记录nums1用过的数，如果找不到，就从没用过的数里填一个。但是超时😔

class Solution {
    // 2 ,7 ,11, 15
    // 1, 4, 10, 11
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int n=nums1.length;
        int[] tmp=new int[n];
        int[] used=new int[n];
        Arrays.fill(used, -1);
        int i=0, j=0;
        for (; i<n; i++) {
            int target=nums2[i];
            boolean isFind=false;
            for (j=0; j<n; j++) {
                if (nums1[j] > target && used[j] == -1) {
                    tmp[i] = nums1[j];
                    used[j] = 1;
                    isFind=true;
                    break;
                }
                
            }
            // //找不到退出吧
            //     if (!isFind)
            //         break;
        }
        j=0;
        i=0;
        while (i<n) {
            if (tmp[i] == 0){
                while (used[j] != -1) {
                    j++;
                }
                tmp[i] = nums1[j];
                j++;
            }
            i++;
        }

        return tmp;
    }
}

思路

使用田忌赛马的思想，为每个nums2[i]找到一个nums1中比它大的最小值。难点是不能更改nums2中的顺序。

重点

！创建一个数组记录nums2的小标，对nums2进行排序，排序的依据是nums2的值的大小从小到大排序。因为不能更改nums2的顺序，那就增加一个可以排序的index数组。

代码

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n=nums1.length;
        Arrays.sort(nums1);
        Integer[] index=new Integer[n];
        for (int i=0; i<n; i++) {
            index[i]=i;
        }
        //使用lamda表达式进行排序，数据类型为封装类，不能是简单类
        Arrays.sort(index, (a, b) -> nums2[a]-nums2[b]);
        //left为nums2最小的一端，right为nums2最大值一端。
        int left=0, right=n-1;
        int[] res = new int[n];
        for (int num : nums1) {
            //如果nums1的值大于nums2小的值，则放在该位置
            //否则放到大值的位置，田忌赛马
            if (num > nums2[index[left]]) {
                res[index[left++]] = num;
            } else {
                res[index[right--]] = num;
            }
        }
        return res;
    }
}