Problem
Given an array A
of integers, for each integer A[i]
we need to choose either x = -K
or x = K
, and add x
to A[i] (only once)
.
After this process, we have some array B
.
Return the smallest possible difference between the maximum value of B
and the minimum value of B
.
Example 1:
Input: A = [1], K = 0 Output: 0 Explanation: B = [1]
Example 2:
Input: A = [0,10], K = 2 Output: 6 Explanation: B = [2,8]
Example 3:
Input: A = [1,3,6], K = 3 Output: 3 Explanation: B = [4,6,3]
Note:
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
Solution: Greedy
Sort the array and compare adjacent numbers.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int smallestRangeII(vector<int>& A, int K) { sort(begin(A), end(A)); int ans = A.back() - A.front(); for (int i = 1; i < A.size(); ++i) { int l = min(A.front() + K, A[i] - K); int h = max(A.back() - K, A[i - 1] + K); ans = min(ans, h - l); } return ans; } }; |
Python3
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua class Solution: def smallestRangeII(self, A, K): A.sort() ans = A[-1] - A[0] for a, b in zip(A[0:-1], A[1:]): l = min(A[0] + K, b - K) h = max(A[-1] - K, a + K) ans = min(ans, h - l) return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment