1.題目描述
給定兩個(gè)大小相等的數(shù)組 nums1 和 nums2，nums1 相對于 nums 的優(yōu)勢可以用滿足 nums1[i] > nums2[i] 的索引 i 的數(shù)目來描述。
返回 nums1 的任意排列，使其相對于 nums2 的優(yōu)勢最大化。
示例 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 進(jìn)行排序，nums1 按照數(shù)組數(shù)字從小到大排序，nums2 則按照數(shù)組中的數(shù)字大小對角標(biāo)進(jìn)行排序，排序后的數(shù)組用 tmp 表示，這樣才能夠根據(jù) tmp 中的角標(biāo)索引查到 nums2 中的數(shù)字及位置。以示例 2 為例，排序后的結(jié)果如下：
在排序完成之后我們開始遍歷數(shù)組進(jìn)行比較，我們使用 L 和 R 兩個(gè)變量指向 nums1 數(shù)組的第 0 位和最后一位，并且讓 L 和 R 在數(shù)組上移動，L 始終表示剩下數(shù)字中最小的，R 表示剩下數(shù)字中最大的數(shù)。
首先比較 nums2 的最大值，即 tmp 數(shù)組的最后一位，此時(shí) num1 中 R 指向 32 等于 nums2 的值 32，由于此時(shí) nums1 沒有比 32 更大的數(shù)了，因此使用 nums1 的“下等馬”即當(dāng)前剩下數(shù)字中最小的數(shù) L 位置的 8 來頂替該位置，然后 L 右移。
然后繼續(xù) nums2 中第二大的數(shù)，此時(shí) nums2 指向 25 小于 nums1 上 R 位置的數(shù) 32，因此使用 32 替換 nums2 中 1 位置的數(shù)。
同理繼續(xù)比較 nums2 上的數(shù)與 nums1 上數(shù)的大小，如果 nums1 更大，則直接使用 R 位置上的數(shù)替換 nums2；如果 nums1 小，則用 nums1 中最小的數(shù)即 L 位置上的數(shù)進(jìn)行替換。
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 測試結(jié)果
通過測試
3.總結(jié)
- 首先對 nums1 按照數(shù)字大小從小到大排序，nums2 按照大小從小到大對索引進(jìn)行排序
- 在 nums1 上使用 L 和 R 始終指向 nums1 中剩余數(shù)字中最小的和最大的數(shù)
- 遇到 nums1 大于 nums2 時(shí)，用 nums1 最大的數(shù)頂替，即 R 位置；遇到 nums1 小于等于 nums2 時(shí)，用 nums1 最小的數(shù)頂替，即 L 位置
