LeetCode 题解工作台
优势洗牌
给定两个长度相等的数组 nums1 和 nums2 ， nums1 相对于 nums2 的 优势 可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。 返回 nums1 的 任意 排列，使其相对于 nums2 的优势最大化。 示例 1： 输入： nums1 = [2,7,1…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
类似田忌赛马。将 , 按照升序排列。然后遍历 中的每个元素 ，若在 中找不到比 小的，则将 与当前 中的最大元素匹配。 时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给定两个长度相等的数组 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 <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109
解题思路
方法一：贪心 + 排序
类似田忌赛马。将 , 按照升序排列。然后遍历 中的每个元素 ，若在 中找不到比 小的，则将 与当前 中的最大元素匹配。
时间复杂度 。
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
t = sorted((v, i) for i, v in enumerate(nums2))
n = len(nums2)
ans = [0] * n
i, j = 0, n - 1
for v in nums1:
if v <= t[i][0]:
ans[t[j][1]] = v
j -= 1
else:
ans[t[i][1]] = v
i += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \log N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Expect clarification on how to match nums1 elements to nums2 efficiently using sorting.
- question_mark
Be ready to explain why a naive greedy from largest to largest might fail on certain permutations.
- question_mark
Demonstrate understanding of invariant tracking during two-pointer scanning to preserve advantage counts.
常见陷阱
外企场景- error
Forgetting to preserve original indices of nums2 while sorting, leading to misaligned assignments.
- error
Assigning largest nums1 elements too early, wasting them on nums2 elements that could be beaten by smaller nums1.
- error
Failing to handle leftover nums1 elements correctly, which can reduce the overall advantage count.
进阶变体
外企场景- arrow_right_alt
Compute the minimum permutation of nums1 that still maximizes advantage instead of any permutation.
- arrow_right_alt
Apply the same two-pointer greedy pattern to a circular array variant where comparisons wrap around.
- arrow_right_alt
Change the condition to nums1[i] >= nums2[i] and adjust the greedy assignment accordingly.