870. 优势洗牌
2022/8/26 6:55:22
本文主要是介绍870. 优势洗牌,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
labuladong 题解思路 难度中等
给定两个大小相等的数组 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]
提示:
1 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 109
class Solution { public: vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(); vector<int> ord(n,0); vector<int> res(n,0); for(int i = 0; i < n;i++) ord[i] = i; sort(ord.begin(),ord.end(),[&](int a, int b){ return nums2[a] > nums2[b]; }); sort(nums1.rbegin(),nums1.rend()); int l=0,r=n-1; for(auto idx:ord) { res[idx] = nums1[l]>nums2[idx]?nums1[l++]:nums1[r--]; } return res; } };
错误解法:用 map 存结果可能会有重复元素。所以应该是按照值排序,然后得到下标的序。
class Solution { public: vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int> val2index; vector<int> nums2_bak = nums2; unordered_map<int,int> val2res; sort(nums2.rbegin(),nums2.rend()); sort(nums1.rbegin(),nums1.rend()); int left = 0; int end = nums2.size() -1; for(int i = 0; i < nums2.size();i++) { if (nums1[left]>nums2[i]) { val2res[nums2[i]] = nums1[left]; left++; } else { val2res[nums2[i]] = nums1[end]; end--; } } vector<int> res; for (auto n2:nums2_bak) { int a = val2res[n2]; res.emplace_back(a); } return res; } };
这篇关于870. 优势洗牌的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?