【力扣 leetcode】870：优势洗牌

素颜马尾好姑娘i 2023-10-09 14:53 33阅读 0赞

## 每日进步 ##

*  **动态类型：**`var`
    
     *  `var`不是关键字，它相当于是一种动态类型。
     *  用`var`定义局部变量时，变量的类型会根据所赋的值来判断。
 *  **int流处理：**`IntStream`
    
     *  `IntStream`：表示处理元素为int类型的管道。
     *  `range(n1, n2)`：创建一个int流，范围从n1到n2-1。
     *  `boxed()`：返回一个流中元素的包装类的流。
     *  `toArray()`：将流中的元素作为一个数组返回。
 *  **下标数组：** 对不能排序的数组使用下标数组进行排序
    
     *      var ids = IntStream.range(0, len).boxed().toArray(Integer[]::new);
              Arrays.sort(ids, (a, b) -> {
                    
                  return nums2[a] - nums2[b];
              });

## 题目 ##

给定两个大小相等的数组 `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 < = 1 <= 1<= `nums1.length`  < = 1 0 5 <= 10^5 <=105
     *  `nums2.length == nums1.length`
     *   0 < = 0 <= 0<= `nums1[i], nums2[i]`  < = 1 0 9 <= 10^9 <=109

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/advantage-shuffle  
> 著作权归领扣网络所有。本文仅供个人学习，非商用。

## 题解 ##

*  本文采用类似田忌赛马的思想：
 *  **认清快马与慢马：** 首先，对`nums1`数组进行排序，因为无法对`nums2`数组排序，故我们采用一个下标数组`ids`间接实现对`nums2`数组的排序。
 *  **田忌赛马：**
    
     *  从`nums1`中最小的元素开始与`nums2`中最小的元素比较。
     *  **慢马赢了慢马，那自然是最好的：** 如果`nums1[i]`大于`ids[i]`中对应的`nums2[ids[i]]`，我们使`ans[ids[left]] = x`
     *  **慢马赢不了慢马，那不如输给快马：** 如果`nums1[i]`小于`ids[i]`中对应的`nums2[ids[i]]`，我们令`ans[ids[right]] = x`，即用`nums1`剩余元素中最小的元素去匹配`nums2`中剩余元素中最大的元素。

class Solution {
        
        public int[] advantageCount(int[] nums1, int[] nums2) {
        
            int len = nums1.length;
            int[] ans = new int[len];
    
            // 排序
            Arrays.sort(nums1);
            var ids = IntStream.range(0, len).boxed().toArray(Integer[]::new);
            Arrays.sort(ids, (a, b) -> {
        
                return nums2[a] - nums2[b];
            });
    
            // 遍历
            int left = 0, right = len - 1;
            for (var x : nums1){
        
                if (x > nums2[ids[left]]){
        
                    ans[ids[left]] = x;
                    left++;
                }
                else{
        
                    ans[ids[right]] = x;
                    right--;
                }
            }
    
            return ans;
        }
    }

执行结果如下图所示：  
![结果][158ca4605d5f468f99341f6bc4662e94.png_pic_center]

[158ca4605d5f468f99341f6bc4662e94.png_pic_center]: https://img-blog.csdnimg.cn/158ca4605d5f468f99341f6bc4662e94.png#pic_center