LeetCode 1984. Minimum difference in student scores

1984. The minimum difference in student scores

To give you one Subscript from 0 Start Array of integers for nums , among nums[i] It means the first one i A student's grade . I'll give you another integer k .

Select any... From the array k A student's grade , Make this k Between scores The highest and Lowest score Of Difference value achieve To minimize the .

Return possible Minimum difference .

Example 1：

 Input ：nums = [90], k = 1
 Output ：0
 explain ： elect  1  A student's grade , have only  1  Methods ：
- [90]  The difference between the highest score and the lowest score is  90 - 90 = 0
 The smallest possible difference is  0

Example 2：

 Input ：nums = [9,4,1,7], k = 2
 Output ：2
 explain ： elect  2  A student's grade , Yes  6  Methods ：
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 4 = 5
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 1 = 8
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 7 = 2
- [9,4,1,7]  The difference between the highest score and the lowest score is  4 - 1 = 3
- [9,4,1,7]  The difference between the highest score and the lowest score is  7 - 4 = 3
- [9,4,1,7]  The difference between the highest score and the lowest score is  7 - 1 = 6
 The smallest possible difference is  2

Tips ：

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 105

Two 、 Method 1

Sort

class Solution {
    
    public int minimumDifference(int[] nums, int k) {
    
        int res = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i + k - 1 < nums.length; i++) {
    
            res = Math.min(res, nums[k + i - 1] - nums[i]);
        }

        return res;
    }
}

Complexity analysis

• Time complexity ：O(nlogn), among n It's an array nums The length of . The time required for sorting is O(nlogn), The time required for subsequent traversal is O(n).

• Spatial complexity ：O(logn), This is the stack space needed for sorting .