Leetcode 870. Advantage Shuffle_综合

文章作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. Description

Advantage Shuffle

2. Solution

Version 1

class Solution {
public:vector<int> advantageCount(vector<int>& A, vector<int>& B) {vector<int> result(A.size());sort(A.begin(), A.end());for(int i = 0; i < B.size(); i++) {int index = findLargerNumber(A, B[i]);result[i] = A[index];A.erase(A.begin() + index);}return result;}private:int findLargerNumber(vector<int>& A, int target) {if(A[A.size() - 1] <= target) {return 0;}for(int i = 0; i < A.size(); i++) {if(A[i] > target) {return i;}}}
};

Version 2

class Solution {
public:vector<int> advantageCount(vector<int>& A, vector<int>& B) {vector<int> result(A.size());sort(A.begin(), A.end());for(int i = 0; i < B.size(); i++) {int index = findLargerNumber(A, B[i]);result[i] = A[index];A.erase(A.begin() + index);}return result;}private:
private:int findLargerNumber(vector<int>& A, int target) {int left = 0;int right = A.size() - 1;while(left < right) {int middle = (left + right) / 2;if(A[middle] <= target) {left = middle + 1;}else {right = middle;}}if(A[right] <= target) {return 0;}else {return right;}}
};

Reference

https://leetcode.com/problems/advantage-shuffle/description/