Problem
Given two arrays A
and B
of equal size, the advantage of A
with respect to B
is the number of indices i
for which A[i] > B[i]
.
Return any permutation of A
that maximizes its advantage with respect to B
.
Example 1:
Input: A = [2,7,11,15], B = [1,10,4,11] Output: [2,11,7,15]
Example 2:
Input: A = [12,24,8,32], B = [13,25,32,11] Output: [24,32,8,12]
Note:
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
Solution: Greedy 田忌赛马
Use the smallest unused number A[j] in A such that A[j] > B[i], if not possible, use the smallest number in A.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 124 ms class Solution { public: vector<int> advantageCount(vector<int>& A, vector<int>& B) { multiset<int> s(begin(A), end(A)); vector<int> ans; for (int b : B) { auto it = s.upper_bound(b); if (it == s.end()) it = s.begin(); ans.push_back(*it); s.erase(it); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment