[LeetCode]Advantage Shuffle

首先我们分析一下最大的match数是怎么来的。输入为A和B，我们先把A和B按照从小到大sort，对于排序过后的数组，如果A[0] > B[0]，那么A中所有的元素都可以match B[0]，如图所示：

对于B[1]，如果A中最小的大于B[1]的数为A[2]，那么只有A[2:N - 1]的数可以match B[1]。如下图所示：

所以对于A[0]和A[1]，其能match的数只有B[0]，也就代表这两个数之中一定有一个失配：

如果我们依次从左向右计算所有A中至少有k个会失配，那么A中可以match B的最大匹配数为N - k。比如题目中给出的例子A = [12, 24, 8, 32], B = [13, 25, 32, 11]，sort之后A = [8, 12, 24, 32], B = [11, 13 25, 32]

1. B[0] = 11可以match的数为12, 24和32，我们取12，8一定失配
2. B[1] = 13可以match 24和32，取24
3. B[3] = 25可以match的数为32，取32
4. B[4] = 32失配

每次取A中大于B[i]的最小数的理由显而易见，如果有多个比B[i]大的数，我们取最小的数可以保证其他较大的数可以继续match比B[i]大的数。用这种思路实现的话，我们需要维护Bsort之前和sort之后的mapping，这不难实现。时间复杂度O(N * log N)，空间复杂度O(N)，代码如下：

	class Solution {
	public:
	vector<int> advantageCount(vector<int>& A, vector<int>& B) {
	int len = A.size(), i = 0, j = 0;
	sort(A.begin(), A.end());
	vector<int> C;
	for(int i = 0; i < len; ++i)C.push_back(i);
	auto comp = [&](const int lhs, const int rhs)
	{
	return B[lhs] < B[rhs];
	};
	sort(C.begin(), C.end(), comp);
	vector<int> res(len, -1);
	while(i < len)
	{
	res[C[j]] = A[i];
	while(i < len && A[i] <= B[C[j]])++i;
	if(i == len)break;
	res[C[j]] = A[i];
	swap(A[i++], A[j++]);
	}
	while(j < len)
	{
	res[C[j]] = A[j];
	++j;
	}
	return res;
	}
	};

view raw Advantage Shuffle_3.cpp hosted with ❤ by GitHub

如果我们不sort，从左向右对于每个B[i]，取A中大于B[i]的最小数也可以。我们需要证明A中失配的数的数目不会变。对于A中在第一种方法中失配的数，在第二种方法也绝不会被匹配上，假设第一种方法A[j]匹配B[i]，那么由于是从小到大匹配，我们尽可能把所有A中大于B[i]小于A[j]的数消耗掉，所以第二种方法中B[i]匹配的数A[k] <= A[j]，那么第一种方法中失配的数在第二种方法必然会继续失配，所以失配的数目不会减少。同时失配的数目也不会增加，因为A[j]匹配B[i]的情况是我们消耗掉了所有可以匹配的小于A[j]的数，那么在这种方法里，显然我们消耗掉的小于A[j]的数是小于等于第一种情况的，所以会继续匹配。匹配的数目不会变，所以答案也不会变。我们用BST存A的值，然后每次对于B的数，去BST中找大于它的最小数，否则assign当前未匹配的最小值。时间复杂度O(N * log N)，空间复杂度O(N)，代码如下：

	class Solution {
	public:
	vector<int> advantageCount(vector<int>& A, vector<int>& B) {
	int len = A.size();
	map<int, int> bst;
	for(const auto& num : A)++bst[num];
	vector<int> res(len, 0);
	for(int i = 0; i < len; ++i)
	{
	auto iter = bst.upper_bound(B[i]);
	if(iter == bst.end())
	{
	res[i] = bst.begin()->first;
	--bst.begin()->second;
	if(bst.begin()->second == 0)
	bst.erase(bst.begin());
	}
	else
	{
	res[i] = iter->first;
	--iter->second;
	if(iter->second == 0)
	bst.erase(iter);
	}
	}
	return res;
	}
	};

view raw Advantage Shuffle_1.cpp hosted with ❤ by GitHub

另外一种贪婪的思路是我们每次去匹配B中最大的值，因为其最难被匹配。这个方法也很好证明，我们从小到大sort了A和B，每次用A中还剩下的最大的数去尝试匹配B中剩下的最大的数，从A[N - 1]尝试匹配B[N - 1]开始，假设我们用了A[k](A[k] <= A[N - 1])尝试匹配B[N - 1]：

• 如果A[k]成功匹配B[N - 1]，那么A[N - 1]必定也可以匹配B[N - 1]。A除去A[k]和B除去B[N - 1]的部分匹配数也不会变
• 如果A[k]成功匹配B[N - 1]，匹配数减1。A除去A[k]和B除去B[N - 1]的部分匹配数最多加1，所以匹配数不会增加

时间复杂度O(N * log N)，空间复杂度O(N)，代码如下：

	class Solution {
	public:
	vector<int> advantageCount(vector<int>& A, vector<int>& B) {
	int len = A.size();
	vector<int> res(len, 0);
	auto comp = [&](const int& lhs, const int& rhs)
	{
	return B[lhs] < B[rhs];
	};
	priority_queue<int, vector<int>, decltype(comp)> pq(comp);
	for(int i = 0; i < len; ++i)pq.push(i);
	sort(A.begin(), A.end());
	int lo = 0, hi = len - 1;
	while(pq.size())
	{
	int idx = pq.top();
	pq.pop();
	if(A[hi] > B[idx])
	res[idx] = A[hi--];
	else
	res[idx] = A[lo++];
	}
	return res;
	}
	};

view raw Advantage Shuffle_2.cpp hosted with ❤ by GitHub

当然这道题本质上是一道最大匹配的问题，我们只需要把A中所有能匹配B[i]的和B[i]连接，那么这就是一个二分图，我们用匈牙利算法跑最大匹配即可。这里只是稍微提一下，不展开讲。