题目
给定两个大小相等的数组 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
解题
方法一:哈希表
思路
本题其实就是田忌赛马,与:【贪心, 二分查找, 双指针】运动员和训练师的最大匹配数【力扣第 87 场双周赛】 有一定的相似性。
具体来说:遍历 nums2
,对于每个元素应该选择 nums1
中比其大的最小数,如果不存在这样的数就选择 nums1
中最小的数。
由于 nums1
中的元素可能会重复,所以可以维护一个可重复的有序集合( 、) ,然后把 nums1
中的所有元素都加入其中以供查找和选择。
代码
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int i = 0; i < n; ++i) {
Integer target = map.higherKey(nums2[i]);
if (target == null) target = map.firstKey();
nums1[i] = target;
map.put(target, map.get(target) - 1);
map.remove(target, 0);
}
return nums1;
}
}
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
multiset<int> st(nums1.begin(), nums1.end());
for (int i = 0; i < n; ++i) {
auto it = st.upper_bound(nums2[i]);
if (it == st.end()) it = st.begin();
nums1[i] = *it;
st.erase(it);
}
return nums1;
}
};
方法二:优先队列(大根堆)
思路
思路与方法一一样,都是要把两个数组都排序,然后从大到小依次对比,如果 nums1[i] > nums2[i]
就保留位置不变,否则就把 nums1[i]
换为 nums1
中最小的元素。
但是由于要通过 nums2
来确定 nums1
,所以 nums2
中元素顺序是不能改变的,所以不能直接对 nums2
进行排序,这里选择维护一个存储着 nums2
中每个元素及其索引的大根堆,且该堆根据元素大小进行排序。
代码
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < n; ++i) pq.offer(new int[]{i, nums2[i]});
Arrays.sort(nums1);
int min = 0, max = n - 1;
int[] ans = new int[n];
while (!pq.isEmpty()) {
int[] tmp = pq.poll();
int i = tmp[0], num = tmp[1];
ans[i] = nums1[max] > num ? nums1[max--] : nums1[min++];
}
return ans;
}
}
auto cmp = [](pair<int, int>& a, pair<int, int>& b) -> bool { return a.second < b.second; };
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < n; ++i) pq.push({i, nums2[i]});
sort(nums1.begin(), nums1.end());
vector<int> ans(n);
int mn = 0, mx = n - 1;
while (!pq.empty()) {
auto pr = pq.top();
int i = pr.first, num = pr.second;
pq.pop();
ans[i] = nums1[mx] <= num ? nums1[mn++] : nums1[mx--];
}
return ans;
}
};
评论区