难度: Medium
原题连接
内容描述
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
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******
今天比赛睡晚了，总共只有35分钟，所以没什么时间，没有想出来，事后证明自己已经非常接近了
这道题的AC率12%左右，其实有点难想出来的
开始我想的是先算出max_num和min_num，再算出它们两的平均值avg_num，然后对于A中的所有数字，如果大于avg_num就减去K，如果小于等于avg_num就加上K。 但是这样是不对的，毕竟这种东西跟我们的K也是有关的
最后想到我们先把A排序，然后A前面一部分比较小的数字全部加上K，后面那部分比较大的数字全部减去K，这样找到一个临界值，使得我们最终的极值最小
所以我们对排序后的A做一个遍历，然后每一轮的最大值会在A[i]+K和A[-1]-K之间取，最小值只会在A[i+1]-K和A[0]+K中取
class Solution(object):
def smallestRangeII(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
if not A or len(A) <= 1:
return 0
if len(A) == 2:
return min(A[-1]-A[0], abs(A[-1]-A[0]-2*K))
K = abs(K)
A.sort()
res = sys.maxsize
for i in range(len(A)-1):
tmp = max(A[i]+K, A[-1]-K) - min(A[i+1]-K, A[0]+K)
res = min(res, tmp)
return min(res, A[-1]-A[0])