给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。返回可能的 最小差值 。
例子
输入： nums = [90], k = 1
输出： 0
解释：选出 1 名学生的分数，仅有 1 种方法：[90] 最高分和最低分之间的差值是 90 - 90 = 0
输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
9 - 4 = 5
9 - 1 = 8
9 - 7 = 2
4 - 1 = 3
7 - 4 = 3
7 - 1 = 6
可能的最小差值是 2
解题思路
双指针
取一个区间内的数据, 典型的滑动窗口问题
拿数组: nums = [1, 5, 3, 1000, 521, 520], k = 2, 举例
首先我们将数组正序排列得到 [1, 3, 5, 520, 521, 1000], 设置窗口滑动
1
2
3
4
5
滑动完之后, 可找出最小值为 1
代码
未翻译版
func minimumDifference(_ nums: [Int], _ k: Int) -> Int {
if nums.count == 1 { return 0 }
var temp = nums.sorted(), last = 0, next = k - 1, res = temp.last! - temp.first!
while next < temp.count {
res = min(res, temp[next] - temp[last])
last += 1
next += 1
}
return res
}
翻译版
func minimumDifference(_ nums: [Int], _ k: Int) -> Int {
// 如果是1直接返回0
if nums.count == 1 { return 0 }
// 定义temp为正序数组, last为后指针, next为前指针, res为区间最小值
var temp = nums.sorted(),
last = 0,
next = k - 1,
res = temp.last! - temp.first!
// 滑动窗口, 直到滑到最后
while next < temp.count {
// 取最小值
res = min(res, temp[next] - temp[last])
// 前, 后指针 +1, 继续滑动
last += 1
next += 1
}
// 返回结果
return res
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
