LeetCode1984. 学生分数的最小差值（打卡Java版）

LeetCode1984. 学生分数的最小差值（打卡Java版）

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 <= 10000 <= nums[i] <= 105

思路

想最小化选择的 ​​k​​ 名学生中最高分和最低分的差值，我们可以在排好序后的数组中连续地进行选择。

这样一来，我们首先对数组nums 进行​​升序排序​​​，随后使用一个大小固定为 ​​k​​​ 的​​滑动窗口​​在 nums 上进行遍历。记滑动窗口的左边界为 i，那么右边界即为 i+k-1，窗口中的 k 名学生最高分和最低分的差值即为 nums[i+k-1] - nums[i]。

最终的答案即为所有 nums[i+k-1] - nums[i]中的最小值。

代码

class Solution { /** * 方法：排序 + 滑动窗口 * 时间复杂度：O(nlogn)，排序O(nlogn)，遍历O(n) * 空间复杂度：O(logn)，排序时使用的栈空间 */ public int minimumDifference(int[] nums, int k) { if (null == nums || nums.length <= 1 || k < 1 || k > nums.length) { return 0; } // 排序 Arrays.sort(nums); int len = nums.length; int ans = Integer.MAX_VALUE; // 滑动窗口 for (int i = 0; i < len - k + 1; i++) { ans = Math.min(nums[i + k - 1] - nums[i], ans); } return ans; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。