[LeetCode] 870. Advantage Shuffle

[grandyang]

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. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= B[i] <= 10^9

这道题给了我们两个数组A和B，让对A进行重排序，使得每个对应对位置上A中的数字尽可能的大于B。这不就是大名鼎鼎的田忌赛马么，但想出高招并不是田忌，而是孙膑，就是孙子兵法的作者，但这 credit 好像都给了田忌，让人误以为是田忌的智慧，不禁想起了高富帅重金买科研成果的冠名权的故事。孙子原话是，“今以君之下驷与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷”。就是自己的下马跟人上马比，稳输不用管，上马跟其中马跑，稳赢，中马跟其下马跑，还是稳赢。那我还全马跟其半马跑，能赢否？不过说的，今天博主所在的城市还真有马拉松比赛，而且博主还报了半马，但是由于身不由己的原因无法去跑，实在是可惜，没事，来日方长，总是有机会的。扯了这么久的犊子，赶紧拉回来做题吧。其实这道题的思路还真是田忌赛马的智慧一样，既然要想办法大过B中的数，那么对于B中的每个数（可以看作每匹马），先在A中找刚好大于该数的数字（这就是为啥中马跟其下马比，而不是上马跟其下马比），用太大的数字就浪费了，而如果A中没有比之大的数字，就用A中最小的数字（用下马跟其上马比，不过略有不同的是此时我们没有上马）。就用这种贪婪算法的思路就可以成功解题了，为了方便起见，就是用一个 MultiSet 来做，相当于一个允许重复的 TreeSet，既允许重复又自带排序功能，岂不美哉！那么遍历B中每个数字，在A进行二分搜索第一个大于的数字，这里使用了 STL 自带的 upper_bound 来做，当然想自己写二分也没问题。然后看，若不存在，则将A中最小的数字加到结果 res 中，否则就将第一个大于的数字加入结果 res 中，参见代码如下：
解法一：

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
		vector<int> res;
		multiset<int> st(A.begin(), A.end());
		for (int i = 0; i < B.size(); ++i) {
			auto it = (*st.rbegin() <= B[i]) ? st.begin() : st.upper_bound(B[i]);
			res.push_back(*it);
			st.erase(it);
		}
		return res;
	}
};

当两个数组都是有序的时候，我们就能快速的直到各自的最大值与最小值，问题就变得容易很多了。比如可以先从B的最大值开始，这是就看A的最大值能否大过B，能的话，就移动到对应位置，不能的话就用最小值，然后再看B的次大值，这样双指针就可以解决问题。所以可以先给A按从小到大的顺序，对于B的话，不能直接排序，因为这样的话原来的顺序就完全丢失了，所以将B中每个数字和其原始坐标位置组成一个 pair 对儿，加入到一个最大堆中，这样B中的最大值就会最先被取出来，再进行上述的操作，这时候就可以发现保存的原始坐标就发挥用处了，根据其坐标就可以直接更新结果 res 中对应的位置了，参见代码如下：
解法二：

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
		int n = A.size(), left = 0, right = n - 1;
		vector<int> res(n);
		sort(A.begin(), A.end());
		priority_queue<pair<int, int>> q;
		for (int i = 0; i < n; ++i) q.push({B[i], i});
		while (!q.empty()) {
			int val = q.top().first, idx = q.top().second; q.pop();
			if (A[right] > val) res[idx] = A[right--];
			else res[idx] = A[left++];
		}
		return res;
	}
};

Github 同步地址:

#870

参考资料：

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

https://leetcode.com/problems/advantage-shuffle/discuss/149831/C%2B%2B-6-lines-greedy-O(n-log-n)

https://leetcode.com/problems/advantage-shuffle/discuss/149822/JAVA-Greedy-6-lines-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中...)