{"id":4067,"date":"2018-09-23T23:02:15","date_gmt":"2018-09-24T06:02:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4067"},"modified":"2018-09-25T08:08:58","modified_gmt":"2018-09-25T15:08:58","slug":"leetcode-908-smallest-range-i","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-908-smallest-range-i\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 908. Smallest Range I"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an array\u00a0A<\/code>\u00a0of integers, for each integer\u00a0A[i]<\/code>\u00a0we may choose any\u00a0x<\/code>\u00a0with\u00a0-K <= x <= K<\/code>, and add\u00a0x<\/code>to\u00a0A[i]<\/code>.<\/p>\n

After this process, we have some array\u00a0B<\/code>.<\/p>\n

Return the smallest possible difference between the maximum value of\u00a0B<\/code>\u00a0and the minimum value of\u00a0B<\/code>.<\/p>\n

\n

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

Input: <\/strong>A = [1]<\/span>, K = 0<\/span>\r\nOutput: <\/strong>0\r\nExplanation<\/strong>: B = [1]<\/span>\r\n<\/pre>\n
\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>A = [0,10]<\/span>, K = 2<\/span>\r\nOutput: <\/strong>6\r\n<\/span>Explanation<\/strong>: B = [2,8]<\/span>\r\n<\/pre>\n
\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>A = [1,3,6]<\/span>, K = 3<\/span>\r\nOutput: <\/strong>0\r\n<\/span>Explanation<\/strong>: B = [3,3,3] or B = [4,4,4]<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length <= 10000<\/code><\/li>\n
  2. 0 <= A[i] <= 10000<\/code><\/li>\n
  3. 0 <= K <= 10000<\/code><\/li>\n<\/ol>\n
    Solution 0: Brute Force (TLE)<\/h1>\n
    Try all pairs<\/p>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(1)<\/p>\n
    Solution 1: Math<\/h1>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(1)<\/p>\n
    Find the min\/max element of the array.<\/p>\n
    min + k v.s. max – k<\/p>\n
    ans = max(0, (max – min) – 2 * k))<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  int smallestRangeI(vector<int>& A, int K) {\r\n    int a_min = *min_element(begin(A), end(A));\r\n    int a_max = *max_element(begin(A), end(A));\r\n    return max(0, (a_max - a_min) - 2 * K);\r\n  }\r\n};<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    # Author: Huahua, 72 ms\r\nclass Solution:\r\n  def smallestRangeI(self, A, K):\r\n    return max(0, max(A) - min(A) - 2 * K);<\/pre>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given an array\u00a0A\u00a0of integers, for each integer\u00a0A[i]\u00a0we may choose any\u00a0x\u00a0with\u00a0-K <= x <= K, and add\u00a0xto\u00a0A[i]. After this process, we have some array\u00a0B. Return…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[413,31,139],"class_list":["post-4067","post","type-post","status-publish","format-standard","hentry","category-math","tag-all-pairs","tag-math","tag-range","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4067","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=4067"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4067\/revisions"}],"predecessor-version":[{"id":4072,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4067\/revisions\/4072"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4067"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4067"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4067"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}