一、题目
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的 任意 排列，使其相对于 nums2 的优势最大化。
二、示例
2.1> 示例 1：
【输入】nums1 = [2,7,11,15], nums2 = [1,10,4,11]
【输出】[2,11,7,15]
2.2> 示例 2：
【输入】nums1 = [12,24,8,32], nums2 = [13,25,32,11]
【输出】[24,32,8,12]
提示：
1<= nums1.length <=105- nums2.length == nums1.length
0<= nums1[i], nums2[i] <=109
三、解题思路
根据题意，我们要找出nums1中的任意排列，使其相对于nums2的优势最大化，那么我们就需要先对其进行排序。因为我们要将对比后的数据直接在nums2中进行替换操作，但是由于nums2中会有概率出现重复元素，所以，我们需要通过对nums2元素的下标orderPos进行排序，来确定唯一性。即：对nums1进行排序，对nums2的下标orderPos进行排序（注意：并不对nums2数组本身进行排序，而是对它的下标数组orderPos进行排序）。具体操作如下图所示：
排序完毕后，我们从后向前开始遍历nums2的下标数组orderPos，由于orderPos已经在上面的步骤中排序了，所以，我们通过orderPos下标再去nums2数组中查找出元素，与nums1的tail元素进行对比。以下图为例，我们发现，nums1[tail] > nums2[1] ，满足“nums1对nums2优势”，所以，将nums1[tail] 的元素4替换nums2[1] 的元素3。具体操作如下图所示：
然后，我们继续向前遍历orderPos数组，此时我们发现 nums1[tail] == nums2[4]，不满足“nums1对nums2优势”，那么我们就取head指向的“当前最小元素”nums1[head]的元素0去替换nums2[4]的元素2。具体操作如下图所示：
我们继续遍历orderPos数组，此时我们发现 nums1[tail] > nums2[0]，满足“nums1对nums2优势”，那么我们就取tail指向的nums1[tail]元素2去替换nums2[0]元素1。具体操作如下图所示：
后面的操作以此类推即可，我就不再画下去了。具体的代码实现，请参见下面部分即可。
四、代码实现
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
Integer[] orderPos = new Integer[nums2.length];
for (int i = 0; i < nums2.length; i++) orderPos[i] = i;
Arrays.sort(orderPos, Comparator.comparingInt(i -> nums2[i])); // 对nums2的“元素位置”进行排序
Arrays.sort(nums1);
int head = 0, tail = nums1.length - 1;
for (int i = orderPos.length - 1; i >= 0; i--) {
if (nums1[tail] > nums2[orderPos[i]]) nums2[orderPos[i]] = nums1[tail--];
else nums2[orderPos[i]] = nums1[head++]; // 否则，将“当前最小值”赋值给它
}
return nums2;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论