1984. 学生分数的最小差值

🟢 🔖 数组 排序 滑动窗口 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example 1:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
[90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Example 2:

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
[9 ,4 ,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
[9 ,4,1 ,7]. The difference between the highest and lowest score is 9 - 1 = 8.
[9 ,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
[9,4 ,1 ,7]. The difference between the highest and lowest score is 4 - 1 = 3.
[9,4 ,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
[9,4,1 ,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

Constraints:

1 <= k <= nums.length <= 1000
0 <= nums[i] <= 10^5

题目大意

给你一个 下标从 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

解题思路

数组排序：
- 由于最大值和最小值的差在有序数组中更容易计算，将数组按照升序排列。
滑动窗口：
- 用一个大小为 k 的窗口遍历排序后的数组。
- 对于窗口的起点为 i：
  - 窗口内的最大值是 nums[i + k - 1]。
  - 窗口内的最小值是 nums[i]。
  - 差值为 nums[i + k - 1] - nums[i]。
维护最小差值：
- 在遍历过程中，记录所有窗口中差值的最小值。
返回最小差值。

复杂度分析

时间复杂度：O(n log n)，其中 n 是数组长度，主要是排序的时间开销。
空间复杂度：O(1)，排序是原地进行的，不占用额外的空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function (nums, k) {
	if (k === 1) return 0; // 当 k 为 1 时，差值一定为 0
	nums.sort((a, b) => a - b); // 排序
	let diff = Infinity;
	for (let i = 0; i <= nums.length - k; i++) {
		diff = Math.min(diff, nums[i + k - 1] - nums[i]); // 计算最小差值
	}
	return diff;
};

1984. 学生分数的最小差值

# 1984. 学生分数的最小差值

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

1984. 学生分数的最小差值

题目

题目大意

解题思路

复杂度分析

代码

相关题目