🥉1984. 学生分数的最小差值

给你一个下标从0开始的整数数组 nums ，其中 nums[i] 表示第i名学生的分数。另给你一个整数k 。从数组中选出任意k名学生的分数，使这k 个分数间最高分和最低分的差值达到最小化 。返回可能的最小差值 。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 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] <= 105

题解

排序

题目很简单，只要理解就有思路。要想获得最小差值，需要先排序整个数组，然后边移动指针，边计算k个数之间的差值，遍历完成之后，最小的那个差值自然就是最小差值。

JavaScript

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

Python

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

复杂度分析

1. 时间复杂度：，其中是数组长度。排序需，后续遍历需。
2. 空间复杂度：，即排序所需要的栈空间。