1984.学生分数的最小差值：排序(类似滑动窗口)

【LetMeFly】1984.学生分数的最小差值：排序(类似滑动窗口)

力扣题目链接：https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/

给你一个 下标从 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

解题方法：排序

将$nums$排序，返回所有长度为$k$的子数组中$diff(last, first)$的最小值即可。

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

C++

/*
 * @LastEditTime: 2026-01-25 10:33:04
 */
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 100000;
        for (int i = 0; i + k - 1 < nums.size(); i++) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-01-25 10:37:04
'''
from typing import List

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))

Java

/*
 * @LastEditTime: 2026-01-25 10:40:30
 */
import java.util.Arrays;

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

Go

/*
 * @LastEditTime: 2026-01-25 10:39:56
 */
package main

import "sort"

func minimumDifference(nums []int, k int) int {
	ans := 100000
    sort.Ints(nums)
	for i := 0; i < len(nums) - k + 1; i++ {
		ans = min(ans, nums[i + k - 1] - nums[i])
	}
	return ans
}

Rust

/*
 * @LastEditTime: 2026-01-25 10:43:39
 */
impl Solution {
    pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut ans = 100000;
        nums.sort();
        for i in 0..nums.len() - k + 1 {
            ans = ans.min(nums[i + k - 1] - nums[i]);
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源