current position:Home>leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
2022-01-31 09:35:09 【Wang Daya】
「 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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201310935075752.html
The sidebar is recommended
- Django ORM details - fields, attributes, operations
- Python web crawler - crawling cloud music review (3)
- Stroke list in python (bottom)
- What cat is the most popular? Python crawls the whole network of cat pictures. Which one is your favorite
- [algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)
- Python shows the progress of downloading files from requests
- Solve the problem that Django celery beat prompts that the database is incorrectly configured and does not support multiple databases
- Bamboolib: this will be one of the most useful Python libraries you've ever seen
- Python quantitative data warehouse construction 3: data drop library code encapsulation
- The source code and implementation of Django CSRF Middleware
guess what you like
-
Python hashlib module
-
The cover of Python 3 web crawler development (Second Edition) has been determined!
-
The introduction method of executing Python source code or Python source code file (novice, please enter the old bird and turn left)
-
[Python basics] explain Python basic functions in detail, including teaching and learning
-
Python web crawler - crawling cloud music review (4)
-
The first step of scientific research: create Python virtual environment on Linux server
-
Writing nmap scanning tool in Python -- multithreaded version
-
leetcode 2057. Smallest Index With Equal Value(python)
-
Bamboolib: this will be one of the most useful Python libraries you've ever seen
-
Python crawler actual combat, requests module, python realizes capturing a video barrage
Random recommended
- [algorithm learning] 1108 IP address invalidation (Java / C / C + + / Python / go / trust)
- Test platform series (71) Python timed task scheme
- Java AES / ECB / pkcs5padding encryption conversion Python 3
- Loguru: the ultimate Python log solution
- Blurring and anonymizing faces using OpenCV and python
- How fast Python sync and async execute
- Python interface automation test framework (basic) -- common data types list & set ()
- Python crawler actual combat, requests module, python realizes capturing video barrage comments of station B
- Python: several implementation methods of multi process
- Sword finger offer II 054 Sum of all values greater than or equal to nodes | 538 | 1038 (Java / C / C + + / Python / go / trust)
- How IOS developers learn python programming 3-operator 2
- How IOS developers learn python programming 2-operator 1
- [Python applet] 8 lines of code to realize file de duplication
- Python uses the pynvml tool to obtain the working status of GPU
- Data mining: Python actual combat multi factor analysis
- Manually compile opencv on MacOS and Linux and add it to Python / C + + / Java as a dependency
- Use Python VTK to batch read 2D slices and display 3D models
- Complete image cutting using Python version VTK
- Python interface automation test framework (basic) -- common data types Dict
- Django (make an epidemic data report)
- Python specific text extraction in actual combat challenges the first step of efficient office
- Daily python, Part 8 - if statement
- Django model class 1
- The same Python code draws many different cherry trees. Which one do you like?
- Python code reading (Chapter 54): Fibonacci sequence
- Django model class 2
- Python crawler Basics
- Mapping 3D model surface distances using Python VTK
- How to implement encrypted message signature and verification in Python -- HMAC
- leetcode 1945. Sum of Digits of String After Convert(python)
- leetcode 2062. Count Vowel Substrings of a String(python)
- Analysis of Matplotlib module of Python visualization
- Django permission management
- Python integrated programming -- visual hot search list and new epidemic situation map
- [Python data collection] scripy realizes picture download
- Python interface automation test framework (basic part) -- loop statement of process control for & while
- Daily python, Chapter 9, while loop
- Van * Python | save the crawled data with docx and PDF
- Five life saving Python tips
- Django frequency control