LC1984. 学生分数的最小差值

LC1984. 学生分数的最小差值

题目描述

给你一个 下标从 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^(5)

参考代码

Python

题目：LC1984. 学生分数的最小差值

难度：简单

作者：许老师-闭着眼睛学数理化

算法：固定滑窗

代码看不懂的地方，请直接在群上提问

class Solution: def minimumDifference(self, nums: List[int], k: int) -> int:

贪心思想，对nums进行排序

nums.sort()

初始化第一个窗口的情况

ans = nums[k-1] - nums[0]

for right, num in enumerate(nums[k:], k):

考虑每一个窗口中的情况

窗口右边界为right，左边界为right-k+1

更新ans

ans = min(ans, num - nums[right-k+1]) return ans Java class Solution { public int minimumDifference(int[] nums, int k) { // Greedy approach, sort nums Arrays.sort(nums);

// Initialize the situation for the first window int ans = nums[k - 1] - nums[0];

for (int right = k, left = 1; right < nums.length; right++, left++) { // Consider each window // The right boundary of the window is 'right', the left boundary is 'right - k + 1' // Update 'ans' ans = Math.min(ans, nums[right] - nums[left]); } return ans; } }

C++ class Solution { public: int minimumDifference(vector<int>& nums, int k) { // Greedy approach, sort nums sort(nums.begin(), nums.end());

// Initialize the situation for the first window int ans = nums[k - 1] - nums[0];

for (int right = k, left = 1; right < nums.size(); right++, left++) { // Consider each window // The right boundary of the window is 'right', the left boundary is 'right - k + 1' // Update 'ans' ans = min(ans, nums[right] - nums[left]); } return ans; } };