给定两个长度相等的数组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 <= nums1.length <= 10^5
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10^9
类似于田忌赛马的思路,想让nums1中尽可能多的下标配对比nums2大。
那么可以首先对两个数组进行排序,这样就可以从下标为0处开始遍历(后面都描述为队首)。
- 如果nums1的队首元素比nums2的队首元素大,那么这就是一组优势。
- 如果nums1的队首元素比nums2的队首元素小,那么就将nums1的队首和nums2的队尾进行配对。(下等马配上等马)
按照上述思路得到的配对优势最大的合理性分析如下:
- 首先,如果nums1队首大于nums2队首,即nums1中当前最差的数也能拿到优势,那么比最差数大的其他数将被尽可能的保留了下来,即在保证优势的同时,保证了后手最大化。
- 其次,虽然可能nums1中的最小数比nums2中第二小甚至更大的数还大,但此时若不与nums2中最小数配对,未来将有一个更大的数和nums2中最小的数配对,大炮打蚊子。
- 而如果nums1队首小于nums2队首,说明无论如何这个数无法产生优势了,那么就去消耗掉nums2中最大的数,为后面更多产生优势提供帮助。
因为最终要返回和原始nums2数组比对的数组,所以在排序后要知道原始下标,通过以下方式可以实现存储排序后的原始索引:
iota(id1.begin(), id1.end(), 0);
iota(id2.begin(), id2.end(), 0);
sort(id1.begin(), id1.end(), [&](int i, int j) { return nums1[i] < nums1[j]; });
sort(id2.begin(), id2.end(), [&](int i, int j) { return nums2[i] < nums2[j]; });
iota
是 C++ 标准库中的一个函数,它用于将一个序列(如向量、列表或数组)中的元素设置为连续的整数值。具体来说,iota
函数将一个范围内的所有元素初始化为一个初始值开始的连续整数序列。
在本例中,上述代码将idx数组初始化为idx[ i ] = i;
在这段代码中,sort
函数用于对容器 idx
中的元素进行排序,这些整数作为索引,指向另一个容器 nums1
中的元素。排序的依据是 nums1
中对应 id1
索引位置的值的大小。
[&](int i, int j) { return nums1[i] < nums1[j]; }
是一个 lambda 表达式,它定义了一个匿名函数,该函数接受两个整数参数 i
和 j
,并返回 nums1[i]
是否小于 nums1[j]
的布尔值。
sort
函数使用这个 lambda 表达式作为比较函数,来确定 id1
中元素的排序顺序。因此,id1
中的元素将根据 nums1
中对应元素的值进行升序排序。
举个例子,假设我们有两个容器:
std::vector<int> nums1 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
std::vector<int> id = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
在 nums1
中,元素是 {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
。
在 id1
中,初始的索引值是 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
,表示 nums1
中每个元素的原始位置。
执行:
std::sort(id.begin(), id.end(), [&](int i, int j) { return nums1[i] < nums1[j]; });
id1
将被重新排序,以反映 nums1
中元素的升序排列。假设排序后的 nums1
元素顺序为 {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
,那么 id
将变为包含这些元素原始索引的升序排列。
排序后,id
变为 {1, 3, 6, 0, 9, 2, 4, 8, 5, 7, 10}
。
完整代码:
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int left = 0;
int right = n-1;
vector<int> id1(n);
vector<int> id2(n);
vector<int> result(n);
iota(id1.begin(), id1.end(), 0);
iota(id2.begin(), id2.end(), 0);
sort(id1.begin(), id1.end(), [&](int i, int j) { return nums1[i] < nums1[j]; });
sort(id2.begin(), id2.end(), [&](int i, int j) { return nums2[i] < nums2[j]; });
for(int i = 0;i < n;++i){
if(nums1[id1[i]] > nums2[id2[left]]){
result[id2[left]] = nums1[id1[i]];
left++;
}else{
result[id2[right]] = nums1[id1[i]];
right--;
}
}
return result;
}
};