Easy

题目描述

给你一个下标从 0 开始的整数数组 nums，其中 nums[i] 表示第 i 名学生的分数。同时给你一个整数 k。

从数组中选出任意 k 名学生的分数，使得这 k 个分数中最高分和最低分的差值达到最小化。

返回可能的最小差值。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数有一种方法：
- [90]。最高分和最低分之间的差值是 90 - 90 = 0 。
可能的最小差值是 0 。

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数有 6 种方法：
- [9,4,1,7]。最高分和最低分之间的差值是 9 - 4 = 5 。
- [9,4,1,7]。最高分和最低分之间的差值是 9 - 1 = 8 。
- [9,4,1,7]。最高分和最低分之间的差值是 9 - 7 = 2 。
- [9,4,1,7]。最高分和最低分之间的差值是 4 - 1 = 3 。
- [9,4,1,7]。最高分和最低分之间的差值是 7 - 4 = 3 。
- [9,4,1,7]。最高分和最低分之间的差值是 7 - 1 = 6 。
可能的最小差值是 2 。

提示：

  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 10^5

解题思路

这道题的核心思路是：为了使选出的k个分数中最高分和最低分的差值最小化，我们需要选择彼此尽可能接近的分数。

方法分析：

  1. 排序 + 滑动窗口（推荐解法）：

    • 首先对数组进行排序，使得相近的分数聚集在一起
    • 排序后，任意连续的k个分数都是彼此最接近的k个分数
    • 使用滑动窗口遍历所有长度为k的连续子数组
    • 对每个窗口，计算最大值与最小值的差值（即窗口右端点减去左端点）
    • 返回所有窗口中的最小差值

  2. 暴力枚举：

    • 枚举所有可能的k个分数的组合
    • 对每个组合计算最大值与最小值的差值
    • 时间复杂度为O(C(n,k) × k)，在数据范围较大时效率较低

实现细节：

  • 排序后，窗口的最大值就是右端点，最小值就是左端点
  • 滑动窗口从索引0开始，到索引n-k结束
  • 特殊情况：当k=1时，差值恒为0

代码实现

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

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

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        if (k == 1) return 0;
        
        Array.Sort(nums);
        
        int minDiff = int.MaxValue;
        for (int i = 0; i <= nums.Length - k; i++) {
            minDiff = Math.Min(minDiff, nums[i + k - 1] - nums[i]);
        }
        
        return minDiff;
    }
}

var minimumDifference = function(nums, k) {
    if (k === 1) return 0;
    
    nums.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    
    for (let i = 0; i <= nums.length - k; i++) {
        minDiff = Math.min(minDiff, nums[i + k - 1] - nums[i]);
    }
    
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n log n)主要消耗在排序操作上，滑动窗口遍历为O(n)
空间复杂度O(1)只使用常数级别的额外空间（不考虑排序的空间消耗）

相关题目