“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

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 the 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 the 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 highest and lowest score is 9-4 = 5. - [9,4,1,7] Highest and lowest score is 9-1 = 8. - [9,4,1,7 [9,4,1,7]. The difference between The highest and lowest score is 4-1 = 3 Highest and lowest score is 7-1 = 3. - [9,4,1,7]. The minimum possible difference is 2.Copy the code

Note:

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

parsing

Given a list of integers indexed from 0, nums[I] represents the ith student’s score, followed by an integer k. Select any k student scores from NUMS in order to minimize the difference between the highest and lowest of the k scores, returning the smallest possible difference.

The simplest is definitely the brute force solution, using the built-in function itertools.combinations to get all the combinations, and then finding the smallest difference of all the combinations. But it’s going to run out of time, because k is at most 1000, so that’s a pretty big combination.

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 the code

The results

Time Limit Exceeded
Copy the code

parsing

Another way to think about it is that to find the difference between the maximum and minimum values of each combination, we simply sort the nums in descending order and compare the difference between the maximum and minimum values of different sublists of k length from left to right. Iterate over each index I in range(k-1, Len (nums)), calculate the difference between the maximum nums[I] and minimum nums[I]-nums[i-k+1] of the current combination, record the minimum value using result, and return result at the end of the traversal.

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 the code

The results

Runtime: 104 ms, Faster than 54.10% of Python online submissions for Minimum Difference Between Highest and Lowest of K Scores. Memory Usage: Submissions in Python online submissions for Minimum Difference Between Highest and Lowest of K Scores.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation