LeetCode

1.题目2.思路3.代码实现（Java）

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：
输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

示例 2：
输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

提示：
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10⁹
0 <= B[i] <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/advantage-shuffle

（1）双指针
① 田忌赛马的故事大家应该都听说过，而本题则可以看作田忌赛马的加强版。我们可以将数组 nums1 的长度和数组 nums2 的长度分别看作田忌和齐威王的马的数量（显然两者相等），而数组中每个元素的值则可以看作每匹马的战斗力（马战斗力越高，跑地越快），并且齐威王的出马顺序已知（即数组 nums2 中的元素顺序），现在需要求田忌的出马顺序（即数组 nums1 的一个排列），使得其赢齐威王的次数最多（即数组 nums1 相对于数组 nums2 的优势最大化）。
② 分析完题目之后，我们的思路如下：分别将田忌和齐威王的马按照战斗力进行排序，然后按照排名来一一比对。如果田忌的马能赢，那就派该马进行比赛，如果赢不了，那就换用战斗力最低的马去比赛，这样可以保证田忌赢齐威王的次数最多，即达到了题目要求的优势最大化。
③ 需要注意的是由于数组 nums1 的排列结果依赖 nums2 的中元素顺序，所以不能直接对 nums2 进行排序，在代码实现中，我们使用了Java中的优先级队列来解决这一问题，详细的使用可以查看代码中的注释。
④ 为了方便比较，我们定义了双指针 left 和 right ，其初始值分别为 0 和 nums1.length-1，它们分别指向经过升序排序后的数组 nums1 的第一个元素和最后一个元素，这样当 nums1[right] 小于数组 nums2 中对应的元素值时，可以直接通过 left 指针找到数组 nums1 中可用的最小值，然后 left 再向右移动一个单位；否则，rigth 向左移动一个单位。

//思路1————双指针
publicint[] advantageCount2(int[] nums1, int[] nums2) {
    int length = nums1.length;
    
    PriorityQueue nums2Queue = new PriorityQueue<>(
            //自定义优先级规则
            (int[] pair1,int[] pair2) -> {
                return pair2[1] - pair1[1];
            }
    );
    for (int i = 0; i < length; i++) {
        //offer(arg):插入一个元素
        nums2Queue.offer(new int[]{i,nums2[i]});
    }
    //将数组nums1升序排序
    Arrays.sort(nums1);
    //定义双指针
    int left = 0,right = length - 1;
    //res用于保存结果
    int[] res = new int[length];
    while(!nums2Queue.isEmpty()){
        //poll():删除一个元素，并返回删除的元素
        int[] pair = nums2Queue.poll();
        //maxVal是数组nums2中的最大值，i是其对应的索引
        int i = pair[0],maxVal = pair[1];
        if(maxVal < nums1[right]){
            //如果nums1[right]胜过maxVal，那就自己上
            res[i] = nums1[right];
            right--;
        }else{
            //如果nums1[right]不敌maxVal，那就用最小值送人头
            res[i] = nums1[left];
            left++;
        }
    }
    return res;
}