題目描述:
給定一個整數陣列 nums(代表學生分數)和整數 k,從中選出 k 個分數,使得最高分和最低分的差值最小。回傳此最小差值。
解題思路:
k 個元素的組合都會有最小的極差(最大值 - 最小值)。k 的滑動窗口掃過排序後的陣列,計算 nums[i + k - 1] - nums[i] 的最小值。直觀理解:排序後選擇的 k 個數字越接近,差值就越小。連續的 k 個數一定比不連續的更優。
時間複雜度:O(n log n) — 排序為主要開銷,滑動窗口掃描為 O(n)。
空間複雜度:O(1) — 若不計排序內部空間,僅使用常數額外空間。
1. Sort nums in ascending order 2. Set minDiff = infinity 3. For i from 0 to n - k: a. diff = nums[i + k - 1] - nums[i] b. minDiff = min(minDiff, diff) 4. Return minDiff
部分排序法 O(n + k log k):使用 nth_element 找到第 k 小的元素,然後只排序前 k 小的元素。但此方法不一定能找到最優解,因為最優窗口不一定包含最小的 k 個。
暴力法 O(C(n,k) * k):枚舉所有 k 個元素的組合,計算每組的極差。時間複雜度過高,不可行。
k 個分數,其標準差最小(而非極差最小),做法如何?