Medium

题目描述

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

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

示例 1:

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2:

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示:

  • 1 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 10^9

解题思路

解题思路

这道题的核心思想是田忌赛马的策略，目标是让 nums1 中尽可能多的元素大于对应位置的 nums2 元素。

贪心策略：

  1. 对于 nums2 中的每个元素，我们要从 nums1 中选择刚好能够"击败"它的最小元素
  2. 如果 nums1 中没有元素能击败当前 nums2 的元素，就用 nums1 中最小的元素去"浪费"

算法步骤：

  1. 将 nums1 排序，方便查找合适的元素
  2. 创建 nums2 的索引数组并按值排序，保持原始位置信息
  3. 对排序后的 nums2，贪心地为每个元素分配 nums1 中的元素：
    • 如果能找到刚好大于它的最小元素，就选择该元素
    • 否则选择 nums1 中剩余的最小元素
  4. 根据原始索引还原结果数组

这种贪心策略确保了我们能获得最大的优势数量，因为我们总是用最小的"有效"元素去击败对手，为更大的对手保留更强的元素。

推荐解法： 排序 + 贪心分配

代码实现

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> result(n);
        
        // 对nums1排序
        sort(nums1.begin(), nums1.end());
        
        // 创建nums2的索引数组并排序
        vector<pair<int, int>> nums2_indexed;
        for (int i = 0; i < n; i++) {
            nums2_indexed.push_back({nums2[i], i});
        }
        sort(nums2_indexed.begin(), nums2_indexed.end());
        
        deque<int> available(nums1.begin(), nums1.end());
        
        // 贪心分配
        for (auto& p : nums2_indexed) {
            int val = p.first;
            int idx = p.second;
            
            // 找到第一个大于val的元素
            auto it = upper_bound(available.begin(), available.end(), val);
            
            if (it != available.end()) {
                result[idx] = *it;
                available.erase(it);
            } else {
                // 没有更大的元素，用最小的
                result[idx] = available.front();
                available.pop_front();
            }
        }
        
        return result;
    }
};

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        result = [0] * n
        
        # 对nums1排序
        nums1.sort()
        
        # 创建nums2的索引数组并排序
        nums2_indexed = [(val, idx) for idx, val in enumerate(nums2)]
        nums2_indexed.sort()
        
        available = nums1[:]
        
        # 贪心分配
        for val, idx in nums2_indexed:
            # 找到第一个大于val的元素
            pos = bisect_right(available, val)
            
            if pos < len(available):
                result[idx] = available.pop(pos)
            else:
                # 没有更大的元素，用最小的
                result[idx] = available.pop(0)
        
        return result

public class Solution {
    public int[] AdvantageCount(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int[] result = new int[n];
        
        // 对nums1排序
        Array.Sort(nums1);
        
        // 创建nums2的索引数组并排序
        var nums2Indexed = new List<(int val, int idx)>();
        for (int i = 0; i < n; i++) {
            nums2Indexed.Add((nums2[i], i));
        }
        nums2Indexed.Sort((a, b) => a.val.CompareTo(b.val));
        
        var available = new List<int>(nums1);
        
        // 贪心分配
        foreach (var (val, idx) in nums2Indexed) {
            // 找到第一个大于val的元素
            int pos = BinarySearch(available, val);
            
            if (pos < available.Count) {
                result[idx] = available[pos];
                available.RemoveAt(pos);
            } else {
                // 没有更大的元素，用最小的
                result[idx] = available[0];
                available.RemoveAt(0);
            }
        }
        
        return result;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var advantageCount = function(nums1, nums2) {
    const n = nums1.length;
    const result = new Array(n);
    
    // 对nums1排序
    nums1.sort((a, b) => a - b);
    
    // 创建nums2的索引数组并排序
    const nums2Indexed = nums2.map((val, idx) => [val, idx]);
    nums2Indexed.sort((a, b) => a[0] - b[0]);
    
    const available = [...nums1];
    
    // 贪心分配
    for (const [val, idx] of nums2Indexed) {
        // 找到第一个大于val的元素
        let pos = binarySearch(available, val);
        
        if (pos < available.length) {
            result[idx] = available.splice(pos, 1)[0];
        } else {
            // 没有更大的元素，用最小的
            result[idx] = available.shift();
        }
    }
    
    return result;
    
    function binarySearch(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)
空间复杂度O(n)

时间复杂度分析：

  • 排序 nums1 和 nums2 索引数组：O(n log n)
  • 对每个元素进行二分查找和删除操作：O(n log n)
  • 总时间复杂度：O(n log n)

空间复杂度分析：

  • 存储排序后的索引数组和可用元素列表：O(n)
  • 结果数组：O(n)
  • 总空间复杂度：O(n)