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

「 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 = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. 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 .

answer

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 .

answer

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 

Original link ：leetcode.com/problems/mi…

Your support is my greatest motivation