1984-学生分数的最小差值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

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

方法一：排序

思路与算法

要想最小化选择的 k 名学生中最高分和最低分的差值，我们一定是在排好序后的数组中连续地进行选择。这是因为在选择时，如果跳过了某个下标 i，那么在选择完毕后，将其中的最高分替换成 nums}[i]，最高分一定不会变大，与最低分的差值同样也不会变大。因此，一定存在有一种最优的选择方案，是连续选择了有序数组中的 k 个连续的元素。

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

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

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int n = nums.Length;
        Array.Sort(nums);
        int ans = int.MaxValue;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.Min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cmp(const void * pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

int minimumDifference(int* nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < numsSize; ++i) {
        ans = MIN(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
var minimumDifference = function(nums, k) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n - k + 1; i++) {
        ans = Math.min(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := math.MaxInt32
    for i, num := range nums[:len(nums)-k+1] {
        ans = min(ans, nums[i+k-1]-num)
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 nums 的长度。排序需要的时间为 O(n \log n)，后续遍历需要的时间为 O(n)。

  • 空间复杂度：O(\log n)，即为排序需要使用的栈空间。

 Comments
On this page
1984-学生分数的最小差值