田忌赛马背后的算法决策

思路分析

给两个长度相等的数组 nums1, nums2，请你重新组织 nums1 中元素的位置，使得 nums1 的⌈优势⌋最大化。如果 nums1[i] > nums2[i]，就是说 nums1 在索引 i 上对 nums[i] 有优势。优势最大化就是说重新组织 nums1，尽可能多的让 nums1[i] > nums2[i]。

比如输入：

nums1 = [12, 24, 8, 32]、nums2 = [13, 25, 32, 11]。你的算法应该返回 [24, 32, 8, 12]，因为这样排列 nums1 的话有三个元素都有⌈优势⌋。

类似于田忌赛马的情景，nums1 就是田忌的🐎，nums2 就是齐王的🐎，数组中的元素就是🐎的战斗力。

最后的策略就是：

将齐王和田忌的🐎按照战斗力排序，然后按照排名一一对比，如果田忌的🐎能赢，那就比赛，如果赢不了，就换个垫底的🐎，保存实例。逻辑如下：

  1. int n = nums1.size();
  2. sort(nums1);
  3. sort(nums2);
  4. for (int i = n - 1; i >= 0; ++i) {
  5.     if (nums1[i] > nums2[i]) {
  6.         // 比赛
  7.     } else {
  8.         // 换个垫底的
  9.     }
  10. }

根据这个思路，需要对两个数组排序，但是 nums2 中元素的顺序不能改变。因为计算结果的顺序依赖 nums2 的顺序，可以利用其他数据结构来辅助。

题目讨论

01 优势洗牌

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

  1. 示例 1：
  3. 输入：A = [2,7,11,15], B = [1,10,4,11]
  4. 输出：[2,11,7,15]
  5. 示例 2：
  7. 输入：A = [12,24,8,32], B = [13,25,32,11]
  8. 输出：[24,32,8,12]
  11. 提示：
  13. 1 <= A.length = B.length <= 10000
  14. 0 <= A[i] <= 10^9
  15. 0 <= B[i] <= 10^9
  17. 来源：力扣（LeetCode）
  18. 链接：https://leetcode-cn.com/problems/advantage-shuffle
  19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于 B 数组的排序，可以使用一个 vector 容器，里面保存一个 pair，一个是索引、一个是索引对应的数据，按照数据从大到小排序即可。代码如下：

vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
    // nums2 降序
    vector<pair<int, int>> maxpq;
    for (int i = 0; i < nums2.size(); ++i) {
        maxpq.push_back(pair<int, int>(i, nums2[i]));
    }
    sort(maxpq.begin(), maxpq.end(), [](const pair<int, int>& a1, const pair<int, int>& a2) {
        return a1.second >= a2.second;
    });

    // nums1 升序
    sort(nums1.begin(), nums2.end());

    int left = 0, right = nums1.size() - 1;
    vector<int> res(nums1.size(), 0);
    for (auto pair : maxpq) {
        int index = pair.first;
        int maxVal = pair.second;
        if (maxVal < nums1[right]) {
            res[index] = nums1[right];
            right--;
        } else {
            res[index] = nums1[left];
            left++;
        }
    }

}