首頁>技術>

題目

給你一個整數陣列 A,對於每個整數 A[i],可以選擇 x = -K 或是 x = K (K 總是非負整數),

並將 x 加到 A[i] 中。

在此過程之後,得到陣列 B。

返回 B 的最大值和 B 的最小值之間可能存在的最小差值。

示例 1:輸入:A = [1], K = 0 輸出:0

解釋:B = [1]

示例 2:輸入:A = [0,10], K = 2 輸出:6

解釋:B = [2,8]

示例 3:輸入:A = [1,3,6], K = 3 輸出:3

解釋:B = [4,6,3]

提示:1 <= A.length <= 10000

0 <= A[i] <= 10000

0 <= K <= 10000

解題思路分析

1、遍歷;時間複雜度O(nlog(n)),空間複雜度O(1)

func smallestRangeII(A []int, K int) int {	sort.Ints(A)	n := len(A)	res := A[n-1] - A[0]	// 排序後,為了最小差值,必定是A[0,i]+K,A[i+1:]-K	// 最小值落在A[0]+K,A[i+1]-K之中	// 最大值落在A[n-1]-K,A[i]+K之中	for i := 0; i < n-1; i++ {		minValue := min(A[0]+K, A[i+1]-K)		maxValue := max(A[n-1]-K, A[i]+K)		res = min(maxValue-minValue, res)	}	return res}func min(a, b int) int {	if a > b {		return b	}	return a}func max(a, b int) int {	if a > b {		return a	}	return b}
總結

Medium題目,排序後,為了最小差值,在一個位置i,對於前一段有A[0,i]+K, 後一段有A[i+1:]-K;

其中最小值落在A[0]+K,A[i+1]-K之中;

其中最大值落在A[n-1]-K,A[i]+K之中;

5
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • GDB偵錯程式原來那麼簡單