题目描述
870. Advantage Shuffle
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
题意:给定两个大小相等的数组A
和B
,A
相对于 B
的优势可以用满足 A[i] > B[i]
的索引 i
的数目来描述。返回 A
的任意排列,使其相对于 B
的优势最大化。
算法1
(贪心,排序,双指针) $O(nlogn)$
题解:这题本质上和Leetcode455分配饼干是一模一样的,只不过我们需要返回一个具体的返回方案。我们依旧将A
和B
进行排序,然后使用双指针算法,对于B[i]
给他分配一个还没有使用过的大于B[i]
的最小的A[j]
。如果当前A[j] > B[i]
,那么说明我们A[j]
是可分配的,我们将A[j]
分配给B[i]
;否则的话A[j]
是不可分配的,那么我们将A[j]
分配给尾指针end
,因为这个B[end]
肯定是不可满足的。
class Solution {
public:
struct item
{
int value,idx;
item(){}
item(int value,int idx):value(value),idx(idx){}
bool operator< (const item &b)
{
return value < b.value;
}
};
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<item> items(n);
vector<int> res(n);
for(int i = 0 ; i < n ; i ++)
items[i] = item(B[i],i);
sort(A.begin(),A.end());
sort(items.begin(),items.end());
for(int i = 0,j = 0,end = n - 1; i < n && j < n; j ++)
{
if(A[j] > items[i].value) res[items[i ++].idx] = A[j];
else res[items[end --].idx] = A[j];
}
return res;
}
};
对啊,问题的本质就是和分配饼干是一样的!赞!