【2022-10-08每日一题】870. 优势洗牌[Medium]
2022-10-08
2分钟阅读时长
2022-10-08每日一题：870. 优势洗牌
难度：Medium
标签：贪心 、 数组 、 双指针 、 排序
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 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
方法一：排序+贪心算法
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func advantageCount(nums1 []int, nums2 []int) []int {
// 构造索引数组
n := len(nums1)
idx1 := make([]int, n)
idx2 := make([]int, n)
for i := 1; i < n; i++ {
idx1[i] = i
idx2[i] = i
}
// 对索引数组升序排序，比较巧妙
sort.Slice(idx1, func (i, j int) bool { return nums1[idx1[i]] < nums1[idx1[j]] })
sort.Slice(idx2, func (i, j int) bool { return nums2[idx2[i]] < nums2[idx2[j]] })
// 贪心构造答案
ans := make([]int, n)
left, right := 0, n - 1
for i := 0; i < n; i++ {
if nums1[idx1[i]] > nums2[idx2[left]] {
ans[idx2[left]] = nums1[idx1[i]]
left++
} else {
ans[idx2[right]] = nums1[idx1[i]] // 放在最大的位置
right--
}
}
return ans
}
田忌赛马
func advantageCount(nums1 []int, nums2 []int) []int {
// 构造索引数组
n := len(nums1)
idx2 := make([]int, n)
for i := 1; i < n; i++ {
idx2[i] = i
}
sort.Ints(nums1)
// 对索引数组升序排序，比较巧妙
sort.Slice(idx2, func (i, j int) bool { return nums2[idx2[i]] < nums2[idx2[j]] })
// 贪心构造答案
ans := make([]int, n)
left, right := 0, n - 1
for i := 0; i < n; i++ {
if nums1[i] > nums2[idx2[left]] {
ans[idx2[left]] = nums1[i] // 用下等马比下等马
left++
} else {
ans[idx2[right]] = nums1[i] // 用下等马比上等马
right--
}
}
return ans
}
复杂度分析
时间复杂度：O(nlog n)，其中 n 是 nums1 的长度。
空间复杂度：O(n)。