鄂州英文网站建设,网站建设公司seo关键词,大学生个人网站制作,微商网站如何做推广1. 题目
给定两个大小相等的数组 A 和 B#xff0c;A 相对于 B 的优势可以用满足 A[i] B[i] 的索引 i 的数目来描述。
返回 A 的任意排列#xff0c;使其相对于 B 的优势最大化。
示例 1#xff1a;
输入#xff1a;A [2,7,11,15], B [1,10,4,11]
输出#xff1…1. 题目
给定两个大小相等的数组 A 和 BA 相对于 B 的优势可以用满足 A[i] B[i] 的索引 i 的数目来描述。
返回 A 的任意排列使其相对于 B 的优势最大化。
示例 1
输入A [2,7,11,15], B [1,10,4,11]
输出[2,11,7,15]示例 2
输入A [12,24,8,32], B [13,25,32,11]
输出[24,32,8,12]提示
1 A.length B.length 10000
0 A[i] 10^9
0 B[i] 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/advantage-shuffle 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 田忌赛马贪心
2.1 二分查找
将A排序对每个Bi 在A中查找比其大的第一个数
class Solution {int l,r,mid;
public:vectorint advantageCount(vectorint A, vectorint B) {sort(A.begin(), A.end());vectorint ans(A.size());int idx;for(int i 0; i B.size(); i){idx binarysearch(A,B[i]);if(idx ! -1){ans[i] A[idx];A.erase(A.begin()idx);}else//没找到比Bi大的用最小的{ans[i] A[0];A.erase(A.begin());}}return ans;}int binarysearch(vectorint A, int n){ //在A中找第一个比n大的l 0; r A.size()-1;while(l r){mid l((r-l)1);if(A[mid] n){if(mid0 || A[mid-1] n)return mid;r mid-1;}elsel mid1;}return -1;}
};2.2 排序双指针
class Solution {
public:vectorint advantageCount(vectorint A, vectorint B) {vectorint ans(A.size());vectorvectorint Bval_idx(B.size(),{-1,-1});int n A.size();for(int i 0; i n; i){Bval_idx[i][0] B[i];Bval_idx[i][1] i;}sort(A.begin(), A.end());sort(Bval_idx.begin(), Bval_idx.end(), [](const auto a, const auto b){return a[0] b[0];});//按数值排序int i 0, j n-1, k 0;for(int k 0; k n; k){if(A[k] Bval_idx[i][0])//最小的能打赢你的最小的{ans[Bval_idx[i][1]] A[k];}else//最小的不能打赢你们那么送给你们最大的吃ans[Bval_idx[j--][1]] A[k];}return ans;}
};
