leetcode 870. Advantage Shuffle 优势洗牌

Problem: 870. Advantage Shuffle 优势洗牌

解题过程

贪心，nums2排序，带上索引的，对nu从小到大遍历的，排序nums1，对每个nu的数字i，从nums1中找到比它大的最小数字，因nu排序了，nums1也排序了，所以两者的索引都只向后移动，并且需要标记nums1的哪些数字被访问过了，最后将nums1中没有被访问过的数字填充到结果数组

Code

class Solution { public: vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(), nums1.end()); vector<pair<int, int>> nu; for(int i = 0; i < nums2.size(); i++) { nu.push_back({nums2[i], i}); } sort(nu.begin(), nu.end()); int n = nums2.size(), j = 0, w; vector<int> ret(n, -1); vector<bool> status(n, false); bool find; for( int i = 0; i < n; i++ ) { find = false; for(w = j; w < n; w++) { if(nu[i].first < nums1[w]) { find = true; break; } } if(find == true) { ret[nu[i].second] = nums1[w]; status[w] = true; j = w + 1; } } vector<int> remain; for( int i = 0; i < n; i++ ) { if(status[i] ==false) { remain.push_back(nums1[i]); } } int cnt = 0; for( int i = 0; i < n; i++ ) { if(ret[i] < 0) { ret[i] = remain[cnt++]; } } return ret; } };