本文涉及的基础知识点

C++算法：滑动窗口及双指针总结
C++贪心

LeetCode870. 优势洗牌

给定两个长度相等的数组 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⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10⁹

C++滑动窗口

如果优势为m，则nums1的最大的m个数，对应nums2最小的m个数的优势一定是m。
nums1和nums2排序。
双指针：指针i = to n-1
指针j:符合 nums1[j] > nums[i]的最小j。

代码

核心代码

class Solution {
		public:
			vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
				sort(nums1.begin(), nums1.end());
				multimap<int, int> mValueIndex;
				for (int i = 0; i < nums2.size(); i++) {
					mValueIndex.emplace(nums2[i], i);
				}
				int j = 0;
				bool bEnd = false;
				vector<int> vRet(nums1.size(),-1);
				for (const auto& [n,i] : mValueIndex) {		
					while ((j < nums1.size()) && (nums1[j] <= n)) { j++; }
					if (j >= nums2.size()) {
						break;
					}
					vRet[i] = nums1[j];
					nums1[j] = -1;
				}
				for (int i = 0, j = 0; i < vRet.size(); i++) {
					if (-1 != vRet[i]) { continue; }
					while (-1 == nums1[j]) { j++; }
					vRet[i] = nums1[j]; j++;
				}
				return vRet;
			}
		};

##　单元测试

vector<int> nums1,nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 2, 7, 11, 15 }, nums2 = { 1, 10, 4, 11 };
			auto res = Solution().advantageCount(nums1, nums2);
			AssertEx(4, Cnt(res,nums2));
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 12,24,8,32 }, nums2 = { 13,25,32,11 };
			auto res = Solution().advantageCount(nums1, nums2);
			AssertEx(3, Cnt(res, nums2));
		}