{"id":9363,"date":"2021-12-31T15:59:40","date_gmt":"2021-12-31T23:59:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9363"},"modified":"2021-12-31T16:04:08","modified_gmt":"2022-01-01T00:04:08","slug":"leetcode-1984-minimum-difference-between-highest-and-lowest-of-k-scores","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-1984-minimum-difference-between-highest-and-lowest-of-k-scores\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1984. Minimum Difference Between Highest and Lowest of K Scores"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array nums<\/code>, where nums[i]<\/code> represents the score of the ith<\/sup><\/code> student. You are also given an integer k<\/code>.<\/p>\n\n\n\n

Pick the scores of any k<\/code> students from the array so that the difference<\/strong> between the highest<\/strong> and the lowest<\/strong> of the k<\/code> scores is minimized<\/strong>.<\/p>\n\n\n\n

Return the minimum<\/strong> possible difference<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [90], k = 1\nOutput:<\/strong> 0\nExplanation:<\/strong> There is one way to pick score(s) of one student:\n- [90<\/u><\/strong>]. The difference between the highest and lowest score is 90 - 90 = 0.\nThe minimum possible difference is 0.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [9,4,1,7], k = 2\nOutput:<\/strong> 2\nExplanation:<\/strong> There are six ways to pick score(s) of two students:\n- [9<\/u><\/strong>,4<\/u><\/strong>,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.\n- [9<\/u><\/strong>,4,1<\/u><\/strong>,7]. The difference between the highest and lowest score is 9 - 1 = 8.\n- [9<\/u><\/strong>,4,1,7<\/u><\/strong>]. The difference between the highest and lowest score is 9 - 7 = 2.\n- [9,4<\/u><\/strong>,1<\/u><\/strong>,7]. The difference between the highest and lowest score is 4 - 1 = 3.\n- [9,4<\/u><\/strong>,1,7<\/u><\/strong>]. The difference between the highest and lowest score is 7 - 4 = 3.\n- [9,4,1<\/u><\/strong>,7<\/u><\/strong>]. The difference between the highest and lowest score is 7 - 1 = 6.\nThe minimum possible difference is 2.<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= k <= nums.length <= 1000<\/code><\/li>
  • 0 <= nums[i] <= 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Sliding Window<\/strong><\/h2>\n\n\n\n
    Sort the array, to minimize the difference, k numbers must be consecutive (i.e, from a subarray). We use a sliding window size of k and try all possible subarrays. 
    Ans = min{(nums[k – 1] – nums[0]), (nums[k] – nums[1]), … (nums[n – 1] – nums[n – k])}<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumDifference(vector& nums, int k) {\n    int ans = INT_MAX;\n    sort(begin(nums), end(nums));\n    for (int i = k - 1; i < nums.size(); ++i)\n      ans = min(ans, nums[i] - nums[i - k + 1]);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[222,215,23],"class_list":["post-9363","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-easy","tag-sliding-window","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9363","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9363"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9363\/revisions"}],"predecessor-version":[{"id":9366,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9363\/revisions\/9366"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}