每日一题:LeetCode:1984.学生分数的最小差值

---

• 每日一题：LeetCode：1984.学生分数的最小差值
  • 时间：2022-02-11
  • 力扣难度：Easy
  • 个人难度：Easy
  • 数据结构：数组
  • 算法：排序、滑动窗口

---

2022-02-11：LeetCode：1984.学生分数的最小差值

1. 题目描述

• 题目：原题链接

  • 给你一个下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
  • 从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分和 最低分的差值达到最小化 。
  • 返回可能的最小差值
  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 105

• 输入输出规范

  • 输入：数组nums，学生个数k
  • 输出：最小差值

• 输入输出示例

  • 输入：nums = [9,4,1,7], k = 2
  • 输出：2

---

2. 方法一：排序 & 滑动窗口

• 思路

  • 本题需要求解出数组中k个元素的中最大值与最小值的差值中的最小差值
  • 根据贪心的思想，可以发现从排序后的数组中选择 k 个连续的元素时，其最大值与最小值的差值才有可能是最小差值
  • 同时，元素的个数 k 是确定的，所以需要维护一个大小为 k 的窗口来计算每个窗口(每组元素)的差值
  • 因此，先对数组进行排序，然后通过滑动窗口的方式来计算每一个差值，并求出最小差值

• 题解

  public int minimumDifference(int[] nums, int k) {
         if(nums == null || nums.length <= 1) return 0;
         Arrays.sort(nums);
         int min = nums[k - 1] - nums[0];
         int index = k;
         while(index < nums.length) {
             min = Math.min(min, nums[index] - nums[index - k + 1]);
             index++;
         }
         return min;
     }

• 复杂度分析：n 是数组的大小

  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(nlogn)$

本文作者： Chthollists
发布时间： 2022-02-11 20:17:36
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1984.学生分数的最小差值
本文链接： https://chthollists.github.io/post/93e53bb3.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！

支持

感谢您的支持

支付宝

微信