当前位置：首页 > news >正文

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

news 2026/5/11 23:26:48

【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] <= 10⁵

解题方法：排序

将n u m s numsnums排序，返回所有长度为k kk的子数组中d i f f ( l a s t , f i r s t ) diff(last, first)diff(last,first)的最小值即可。

时间复杂度O ( N 2 ) O(N^2)O(N2)
空间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)

AC代码

C++

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

Python

''' LastEditTime: 2026-01-25 10:37:04 '''fromtypingimportListclassSolution:defminimumDifference(self,nums:List[int],k:int)->int:nums.sort()returnmin(nums[i+k-1]-nums[i]foriinrange(len(nums)-k+1))

Java

/* * @LastEditTime: 2026-01-25 10:40:30 */importjava.util.Arrays;classSolution{publicintminimumDifference(int[]nums,intk){intans=100000;Arrays.sort(nums);for(inti=0;i+k-1<nums.length;i++){ans=Math.min(ans,nums[i+k-1]-nums[i]);}returnans;}}

Go

/* * @LastEditTime: 2026-01-25 10:39:56 */packagemainimport"sort"funcminimumDifference(nums[]int,kint)int{ans:=100000sort.Ints(nums)fori:=0;i<len(nums)-k+1;i++{ans=min(ans,nums[i+k-1]-nums[i])}returnans}

Rust

/* * @LastEditTime: 2026-01-25 10:43:39 */implSolution{pubfnminimum_difference(mutnums:Vec<i32>,k:i32)->i32{letk=kasusize;letmutans=100000;nums.sort();foriin0..nums.len()-k+1{ans=ans.min(nums[i+k-1]-nums[i]);}ans}}