[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)，代码如下：

如果我们不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)，代码如下：

另外一种贪婪的思路是我们每次去匹配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)，代码如下：

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