# leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores（python）

2022-01-31 09:35:09

「 This is my participation 11 The fourth of the yuegengwen challenge 11 God , Check out the activity details ：2021 One last more challenge

### describe

``````You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.
Copy code ``````

Example 1:

``````Input: nums = , k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- . The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.
Copy code ``````

Example 2:

``````Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.
Copy code ``````

Note:

``````1 <= k <= nums.length <= 1000
0 <= nums[i] <= 10^5
Copy code ``````

### analysis

According to the meaning , Give an example from 0 List of integers to start indexing nums , Among them nums[i] It means No i A student's score , Then we give an integer k . from nums Select any k A student's score , So that k Minimize the difference between the highest and lowest scores , Returns the smallest possible difference .

The simplest solution must be violence , Use built-in functions itertools.combinations Get all the combinations , Then find the minimum difference of all combinations . But the result must be timeout , How can there be such a simple question , because k The biggest is 1000 , The result of that combination is big .

``````class Solution(object):
def minimumDifference(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if k == 1: return 0
if k>=len(nums): return max(nums) - min(nums)
result = 10**5
for cb in itertools.combinations(nums, k):
result = min(result, max(cb) - min(cb))
return result

Copy code ``````

### Running results

``````Time Limit Exceeded
Copy code ``````

### analysis

You can change your mind , Because we need to find the difference between the maximum and minimum of each combination , We just have to take nums Sort from small to large , Then compare from left to right k The difference between the maximum value and the minimum value of different sub lists of length , Traverse range(k-1, len(nums)) Each index in i , Calculate the maximum value of the current combination nums[i] Minimum value nums[i]-nums[i-k+1] The difference between the , And use result Record minimum , Return after traversal result that will do .

``````class Solution(object):
def minimumDifference(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if k == 1: return 0
if k>=len(nums): return max(nums) - min(nums)
result = 10**5
nums.sort()
print(nums)
for i in range(k-1, len(nums)):
result = min(result, nums[i]-nums[i-k+1])
return result

Copy code ``````

### Running results

``````Runtime: 104 ms, faster than 54.10% of Python online submissions for Minimum Difference Between Highest and Lowest of K Scores.
Memory Usage: 13.7 MB, less than 9.84% of Python online submissions for Minimum Difference Between Highest and Lowest of K Scores.
Copy code ``````