{"id":4081,"date":"2018-09-26T08:35:50","date_gmt":"2018-09-26T15:35:50","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4081"},"modified":"2018-09-26T08:36:04","modified_gmt":"2018-09-26T15:36:04","slug":"leetcode-910-smallest-range-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-910-smallest-range-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 910. Smallest Range II"},"content":{"rendered":"

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

Given an array\u00a0A<\/code>\u00a0of integers, for each integer\u00a0A[i]<\/code>\u00a0we need to choose\u00a0either\u00a0x = -K<\/code>\u00a0or\u00a0x = K<\/code><\/strong>, and add\u00a0x<\/code>\u00a0to\u00a0A[i]\u00a0(only once)<\/strong><\/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

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

Input: <\/strong>A = [1]<\/span>, K = 0<\/span>\r\nOutput: <\/strong>0<\/span>\r\nExplanation<\/strong>: B = [1]\r\n<\/pre>\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]\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>A = [1,3,6]<\/span>, K = 3<\/span>\r\nOutput: <\/strong>3<\/span>\r\nExplanation<\/strong>: B = [4,6,3]\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: Greedy<\/strong><\/h1>\n
    Sort the array and compare adjacent numbers.<\/p>\n
    Time complexity: O(nlogn)<\/p>\n
    Space complexity: O(1)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  int smallestRangeII(vector<int>& A, int K) {    \r\n    sort(begin(A), end(A));    \r\n    int ans = A.back() - A.front();\r\n    for (int i = 1; i < A.size(); ++i) {      \r\n      int l = min(A.front() + K, A[i] - K);\r\n      int h = max(A.back() - K, A[i - 1] + K);\r\n      ans = min(ans, h - l);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\r\nclass Solution:\r\n  def smallestRangeII(self, A, K):\r\n    A.sort()\r\n    ans = A[-1] - A[0]\r\n    for a, b in zip(A[0:-1], A[1:]):\r\n      l = min(A[0] + K, b - K)\r\n      h = max(A[-1] - K, a + K)\r\n      ans = min(ans, h - l)\r\n    return ans<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given an array\u00a0A\u00a0of integers, for each integer\u00a0A[i]\u00a0we need to choose\u00a0either\u00a0x = -K\u00a0or\u00a0x = K, and add\u00a0x\u00a0to\u00a0A[i]\u00a0(only once). After this process, we have some array\u00a0B.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,139,417],"class_list":["post-4081","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-range","tag-smallest","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4081","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=4081"}],"version-history":[{"count":1,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4081\/revisions"}],"predecessor-version":[{"id":4082,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4081\/revisions\/4082"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}