当前位置：首页 > news >正文

面试必看：优势洗牌

news 2026/3/26 21:19:03

贪心+双指针求解优势洗牌问题（C++ 实现）

题目描述

给定两个长度相等的数组nums1和nums2，定义nums1相对于nums2的优势为满足nums1[i] > nums2[i]的索引i的数量。要求返回nums1的任意一个排列，使得该排列相对于nums2的优势最大化。

问题分析

结合题目要求和数据特征，我们可以先梳理核心约束与解题思路：

两个数组长度相同，排列后元素需按索引一一对应匹配；
目标是最大化满足nums1[i] > nums2[i]的索引数量，本质是用最优的匹配策略实现收益最大化；
直接暴力枚举所有排列会产生极高的时间复杂度，无法高效处理较大数据量，因此需要选择更优的算法方案。

结合问题特征，贪心算法+双指针是适配该场景的最优解：贪心策略用于保证每一步选择都能获取当前最优收益，双指针用于高效遍历匹配元素，整体算法可以在线性遍历结合排序的基础上完成计算。

算法思路

核心策略

采用贪心匹配原则：用nums1中最小的可用大数去匹配nums2中对应元素，无法满足大小关系时，用nums1中最小的数去填充，最大化有效匹配数量的同时，减少优质元素的浪费。

具体步骤

数组预处理
- 对nums1执行升序排序，方便通过双指针快速获取当前最大/最小可用元素；
- 为nums2构建(值, 原索引)的键值对数组，再对该数组执行升序排序。保留原索引是为了保证最终结果能对应到题目要求的原始位置。
双指针初始化
定义左指针left指向排序后nums1的起始位置（最小值），右指针right指向排序后nums1的末尾位置（最大值）。
逆序遍历匹配
从大到小遍历处理后的nums2数组，依次判断当前元素：
- 若nums1的当前最大值大于nums2的当前元素，将该最大值填入结果数组的对应原始索引，右指针左移；
- 若不满足大小关系，说明当前最大元素也无法形成优势，改用nums1的当前最小值填充，左指针右移。
输出结果
遍历完成后，结果数组即为满足条件的nums1最优排列。

C++ 实现代码

#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:vector<int>advantageCount(vector<int>&nums1,vector<int>&nums2){// 获取数组长度intn=nums1.size();// 初始化结果数组，长度与输入数组一致vector<int>res(n,0);// 存储nums2的(值, 原索引)对，保留原始位置信息vector<pair<int,int>>nums2_temp;for(inti=0;i<n;++i){nums2_temp.emplace_back(nums2[i],i);}// 对nums1升序排序sort(nums1.begin(),nums1.end());// 对nums2的键值对数组按值升序排序sort(nums2_temp.begin(),nums2_temp.end());// 双指针初始化：left指向nums1最小值，right指向nums1最大值intleft=0;intright=n-1;// 逆序遍历排序后的nums2_temp，从大元素开始匹配for(inti=n-1;i>=0;--i){intval=nums2_temp[i].first;// nums2当前元素值intindex=nums2_temp[i].second;// 该元素在原数组中的索引// 贪心选择：能用大值匹配就用大值，否则用小值填充if(val<nums1[right]){res[index]=nums1[right];--right;}else{res[index]=nums1[left];++left;}}returnres;}};