Sum of Mutated Array Closest to Target
给一个数组和一个target, 求一个数字n, 把数组中所有大于n的数字都替换成n以后, 数组的和与target最接近. 这个题是找最接近target的一个数字n, 那么用二叉搜索找即可, 设lo是0, hi是target, 那么mid就是中间假设的答案, 这个答案可以通过题意的改变数组后, 找到和target的差值, 因为我们知道mid是单调递增的, 所以可以用二叉搜索.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public int findBestValue(int[] arr, int target) { int lo = 0; int hi = target; while(lo <= hi) { int mid = lo + (hi - lo) / 2; int tmp = sum(arr, mid); if(tmp == target) return mid; else if(tmp > target) hi = mid - 1; else lo = mid + 1; } if(Math.abs(sum(arr, lo) - target) >= Math.abs(sum(arr, lo-1) - target)) return lo-1; else return lo; } private int sum(int[] arr, int n) { int sum = 0; for(int i = 0; i < arr.length; i++) { if(arr[i] > n) { sum += n; } else { sum += arr[i]; } } return sum; } } |