1984. 學(xué)生分?jǐn)?shù)的最小差值

給你一個(gè) 下標(biāo)從 0 開始 的整數(shù)數(shù)組 nums ，其中 nums[i] 表示第 i 名學(xué)生的分?jǐn)?shù)。另給你一個(gè)整數(shù) k 。

從數(shù)組中選出任意 k 名學(xué)生的分?jǐn)?shù)，使這 k 個(gè)分?jǐn)?shù)間 最高分 和 最低分 的 差值 達(dá)到 最小化 。

返回可能的 最小差值 。

示例 1：輸入：nums = [90], k = 1 輸出：0 解釋：選出 1 名學(xué)生的分?jǐn)?shù)，僅有 1 種方法： - [90] 最高分和最低分之間的差值是 90 - 90 = 0 可能的最小差值是 0示例 2：輸入：nums = [9,4,1,7], k = 2 輸出：2 解釋：選出 2 名學(xué)生的分?jǐn)?shù)，有 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

解題思路

我們先對(duì)數(shù)組按從小到大的順序進(jìn)行排序，枚舉長(zhǎng)度為k的所有區(qū)間，因?yàn)槲覀兊臄?shù)組是有序的，因此我們每一個(gè)區(qū)間也是有序的，根據(jù)這個(gè)特性，我們可以得出區(qū)間的首尾元素就是區(qū)間內(nèi)的最大值和最小值，因此 最高分 和 最低分 的 差值 只需要將區(qū)間末尾元素，減去區(qū)間頭元素即可，并且在所有可能的區(qū)間內(nèi)選出最小差值的區(qū)間。

代碼

class Solution { public:int minimumDifference(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int res(INT_MAX);for (int i = 0; i+k <= nums.size(); ++i) {res=min(nums[i+k-1]-nums[i],res);}return res;} };

總結(jié)

以上是生活随笔為你收集整理的1984. 学生分数的最小差值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。