1.题目描述
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 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]
2.解题思路与代码
2.1 解题思路
这道题的核心思想就是田忌赛马，让下等马与上等马比较，这样就能保证其他的对比能够获胜。首先我们对 nums1 和 nums2 进行排序，nums1 按照数组数字从小到大排序，nums2 则按照数组中的数字大小对角标进行排序，排序后的数组用 tmp 表示，这样才能够根据 tmp 中的角标索引查到 nums2 中的数字及位置。以示例 2 为例，排序后的结果如下：
在排序完成之后我们开始遍历数组进行比较，我们使用 L 和 R 两个变量指向 nums1 数组的第 0 位和最后一位，并且让 L 和 R 在数组上移动，L 始终表示剩下数字中最小的，R 表示剩下数字中最大的数。
首先比较 nums2 的最大值，即 tmp 数组的最后一位，此时 num1 中 R 指向 32 等于 nums2 的值 32，由于此时 nums1 没有比 32 更大的数了，因此使用 nums1 的“下等马”即当前剩下数字中最小的数 L 位置的 8 来顶替该位置，然后 L 右移。
然后继续 nums2 中第二大的数，此时 nums2 指向 25 小于 nums1 上 R 位置的数 32，因此使用 32 替换 nums2 中 1 位置的数。
同理继续比较 nums2 上的数与 nums1 上数的大小，如果 nums1 更大，则直接使用 R 位置上的数替换 nums2；如果 nums1 小，则用 nums1 中最小的数即 L 位置上的数进行替换。
2.2 代码
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Integer[] tmp = new Integer[nums2.length];
for (int i = 0; i < nums2.length; i++) {
tmp[i] = i;
}
Arrays.sort(tmp, (o1, o2) -> nums2[o1] - nums2[o2]);
int L = 0;
int R = nums1.length - 1;
for (int i = nums2.length - 1; i >= 0; i--) {
if (nums1[R] > nums2[tmp[i]]) {
nums2[tmp[i]] = nums1[R];
R--;
} else {
nums2[tmp[i]] = nums1[L];
L++;
}
}
return nums2;
}
}
2.3 测试结果
通过测试
3.总结
- 首先对 nums1 按照数字大小从小到大排序，nums2 按照大小从小到大对索引进行排序
- 在 nums1 上使用 L 和 R 始终指向 nums1 中剩余数字中最小的和最大的数
- 遇到 nums1 大于 nums2 时，用 nums1 最大的数顶替，即 R 位置；遇到 nums1 小于等于 nums2 时，用 nums1 最小的数顶替，即 L 位置
