网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 1984. 学生分数的最小差值 ，难度为 简单。
Tag : 「二分」、「滑动窗口」
给你一个 下标从 00 开始 的整数数组 numsnums ，其中 nums[i]nums[i] 表示第 ii 名学生的分数。另给你一个整数 kk 。
从数组中选出任意 kk 名学生的分数，使这 kk 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
示例 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 <= 10001<=k<=nums.length<=1000
- 0 <= nums[i] <= 10^50<=nums[i]<=105
排序 + 滑动窗口
从 nn 个元素里找 kk 个，使得 kk 个元素最大差值最小。
最大值最小化问题容易想到「二分」，利用答案本身具有「二段性」，来将原本的求解问题转化为判断定问题。
回到本题，容易证明，这 kk 个元素必然是有序数组中（排序后）的连续段。反证法，若最佳 kk 个选择不是连续段，能够调整为连续段，结果不会变差。
因此我们可以先对 numsnums 进行排序，然后扫描所有大小为 kk 的窗口，直接找到答案，而无须使用「二分」。
代码（二分答案代码见 P2P2）：
class Solution { public int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int n = nums.length, ans = nums[k - 1] - nums[0]; for (int i = k; i < n; i++) { ans = Math.min(ans, nums[i] - nums[i - k + 1]); } return ans; } } 复制代码
class Solution { int[] nums; int k; public int minimumDifference(int[] _nums, int _k) { nums = _nums; k = _k; Arrays.sort(nums); int l = 0, r = 100010; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return r; } boolean check(int x) { int n = nums.length, ans = nums[k - 1] - nums[0]; for (int i = k; i < n && ans > x; i++) { ans = Math.min(ans, nums[i] - nums[i - k + 1]); } return ans <= x; } } 复制代码
- 时间复杂度：排序复杂度为 O(n\log{n})O(nlogn)；遍历得到答案复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
- 空间复杂度：O(\log{n})O(logn)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1894 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
