LeetCode 870. 优势洗牌

Categories:

题目描述
思路分析
1. 解法一：贪心 + 排序（推荐）
相似题目

题目描述

✅ 870. 优势洗牌

思路分析

解法一：贪心 + 排序（推荐）

核心思路：

将 nums1 排序，并将 nums2 按值排序保留原下标。

从 nums2 的大值开始匹配：

若 nums1 最大值能胜过，则用最大值；否则用最小值“垫底”。

还原为原顺序。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于排序与结果数组。

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] res = new int[n];

        Arrays.sort(nums1);
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (a, b) -> Integer.compare(nums2[a], nums2[b]));

        int left = 0;
        int right = n - 1;

        // 从大到小匹配 nums2
        for (int k = n - 1; k >= 0; k--) {
            int i = idx[k];
            if (nums1[right] > nums2[i]) {
                res[i] = nums1[right--];
            } else {
                res[i] = nums1[left++];
            }
        }

        return res;
    }
}

func advantageCount(nums1 []int, nums2 []int) []int {
	n := len(nums1)
	res := make([]int, n)
	sort.Ints(nums1)

	idx := make([]int, n)
	for i := 0; i < n; i++ {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return nums2[idx[i]] < nums2[idx[j]] })

	left, right := 0, n-1

	// 从大到小匹配 nums2
	for k := n - 1; k >= 0; k-- {
		i := idx[k]
		if nums1[right] > nums2[i] {
			res[i] = nums1[right]
			right--
		} else {
			res[i] = nums1[left]
			left++
		}
	}

	return res
}

相似题目

题目	难度	考察点
455. 分发饼干	简单	贪心
870. 优势洗牌	中等	贪心
1029. 两地调度	中等	贪心
1353. 最多可以参加的会议数目	中等	贪心
1402. 做菜顺序	困难	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/34986837