阅读视图

贪心（Python/Java/C++/C/Go/JS/Rust）

2021年8月29日 12:07

为方便计算差值，先把 $\textit{nums}$ 从小到大排序。

把 $\textit{nums}$ 中的元素画在一维数轴上。如果 $\textit{nums}[i]$ 是 $k$ 个数中的最大值，那么最小值的下标至多为 $i-k+1$（要在最小值和最大值之间再选 $k-2$ 个数）。但最小值越小，差值越大，所以最小值的下标恰好为 $i-k+1$ 是最优的。

枚举最大值的下标 $i = k-1,k,k+1,\ldots, n-1$，计算差值 $\textit{nums}[i] - \textit{nums}[i-k+1]$ 的最大值，即为答案。

class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
return min(nums[i] - nums[i - k + 1] for i in range(k - 1, n))

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(mx - mn for mx, mn in zip(nums[k - 1:], nums))

class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
for (int i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
}

class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
ranges::sort(nums);
int ans = INT_MAX;
for (int i = k - 1; i < nums.size(); i++) {
ans = min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}

int minimumDifference(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int ans = INT_MAX;
for (int i = k - 1; i < numsSize; i++) {
ans = MIN(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}

func minimumDifference(nums []int, k int) int {
slices.Sort(nums)
ans := math.MaxInt
for i := k - 1; i < len(nums); i++ {
ans = min(ans, nums[i]-nums[i-k+1])
}
return ans
}

var minimumDifference = function(nums, k) {
nums.sort((a, b) => a - b);
let ans = Infinity;
for (let i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
};

impl Solution {
pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let k = k as usize;
let mut ans = i32::MAX;
for i in k - 1..nums.len() {
ans = ans.min(nums[i] - nums[i - k + 1]);
}
ans
}
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

证明，交换论证法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2021年5月30日 00:10

你可能猜了一个结论：把最小的数和最大的数配对，把第二小的数和第二大的数配对，依此类推。注意题目保证 $n$ 是偶数。

但是，如何证明这样做是对的？

设 $\textit{nums}$ 排序后的结果为 $a_1\le a_2\le \cdots \le a_n$。

首先证明，$a_1$ 与 $a_n$ 配对是最优的。

设 $a_i$ 和 $a_j$ 是数组中的另外两个数，考虑如下两种配对方案：

$(a_1,a_i)$ 和 $(a_j,a_n)$。最大数对和为 $M_1 = \max(a_1+a_i,a_j+a_n,其他数对和)$。
$(a_1,a_n)$ 和 $(a_i,a_j)$。最大数对和为 $M_2 = \max(a_1+a_n,a_i+a_j,其他数对和)$。

由于 $a_1\le a_j$，$a_i\le a_n$，所以 $a_1+a_i\le a_j+a_n$，所以 $M_1 = \max(a_j+a_n,其他数对和)$。

由于 $a_1+a_n\le a_j+a_n$ 且 $a_i+a_j\le a_j+a_n$，所以 $\max(a_1+a_n,a_i+a_j)\le a_j+a_n$，所以 $M_2\le M_1$。

这意味着，对于任意最优配对方案，将其调整为 $a_1$ 和 $a_n$ 配对，不会让最大数对和变得更大。所以存在最优配对方案，其中 $a_1$ 和 $a_n$ 是配对的。

去掉 $a_1$ 和 $a_n$（已配对），问题变成一个规模更小的子问题（$n-2$ 个数），同理可得其他数的配对方式。

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[i] + nums[-1 - i] for i in range(n // 2))

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
}

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int minPairSum(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = 0;
    for (int i = 0; i < numsSize / 2; i++) {
        ans = MAX(ans, nums[i] + nums[numsSize - 1 - i]);
    }
    return ans;
}

func minPairSum(nums []int) (ans int) {
slices.Sort(nums)
n := len(nums)
for i, x := range nums[:n/2] {
ans = max(ans, x+nums[n-1-i])
}
return
}

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n / 2; i++) {
        ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
    }
    return ans;
};

impl Solution {
    pub fn min_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n / 2 {
            ans = ans.max(nums[i] + nums[n - 1 - i]);
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

专题训练

见下面贪心题单的「§1.2 单序列配对」和「§1.7 交换论证法」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府