題目

給你一個整數陣列 arr 和一個目標值 target ，請你返回一個整數 value ，

使得將陣列中所有大於 value 的值變成 value 後，

陣列的和最接近 target （最接近表示兩者之差的絕對值最小）。

如果有多種使得和最接近 target 的方案，請你返回這些整數中的最小值。

請注意，答案不一定是 arr 中的數字。

示例 1：輸入：arr = [4,9,3], target = 10 輸出：3

解釋：當選擇 value 為 3 時，陣列會變成 [3, 3, 3]，和為 9 ，這是最接近 target 的方案。

示例 2：輸入：arr = [2,3,5], target = 10 輸出：5

示例 3：輸入：arr = [60864,25176,27249,21296,20204], target = 56803 輸出：11361

提示：

1 <= arr.length <= 10^4

1 <= arr[i], target <= 10^5

解題思路分析

1、二分查詢；時間複雜度O(nlog(n))，空間複雜度O(n)

func findBestValue(arr []int, target int) int {	sort.Ints(arr)	n := len(arr)	temp := make([]int, n+1)	for i := 1; i <= n; i++ {		temp[i] = temp[i-1] + arr[i-1]	}	right := arr[n-1]	res := 0	diff := target	for i := 1; i <= right; i++ {		index := sort.SearchInts(arr, i)		if index < 0 {			index = abs(index) - 1		}		total := temp[index] + (n-index)*i		if abs(total-target) < diff {			diff = abs(total - target)			res = i		}	}	return res}func abs(a int) int {	if a < 0 {		return -a	}	return a}

2、二分查詢；時間複雜度O(nlog(n))，空間複雜度O(n)

func findBestValue(arr []int, target int) int {	sort.Ints(arr)	n := len(arr)	temp := make([]int, n+1)	for i := 1; i <= n; i++ {		temp[i] = temp[i-1] + arr[i-1]	}	left, right := 0, arr[n-1]	res := 0	for left <= right {		mid := left + (right-left)/2		index := sort.SearchInts(arr, mid)		if index < 0 {			index = abs(index) - 1		}		total := temp[index] + (n-index)*mid		if total <= target {			res = mid			left = mid + 1		} else {			right = mid - 1		}	}	a := getSum(arr, res)	b := getSum(arr, res+1)	if abs(a-target) > abs(b-target) {		return res + 1	}	return res}func getSum(nums []int, target int) int {	res := 0	for i := 0; i < len(nums); i++ {		if nums[i] <= target {			res = res + nums[i]		} else {			res = res + target		}	}	return res}func abs(a int) int {	if a < 0 {		return -a	}	return a}

3、遍歷；時間複雜度O(n^2)，空間複雜度O(1)

func findBestValue(arr []int, target int) int {	sort.Ints(arr)	n := len(arr)	res := target / n	diff := target + 1	for {		a := getSum(arr, res)		if diff <= abs(target-a) {			return res - 1		}		diff = abs(target - a)		res = res + 1	}	return res}func getSum(nums []int, target int) int {	res := 0	for i := 0; i < len(nums); i++ {		if nums[i] <= target {			res = res + nums[i]		} else {			res = res + target		}	}	return res}func abs(a int) int {	if a < 0 {		return -a	}	return a}

總結

Medium題目，計算字首和，然後採用二分查詢