Sum of Mutated Array Closest to Target
给一个数组和一个target, 求一个数字n, 把数组中所有大于n的数字都替换成n以后, 数组的和与target最接近. 这个题是找最接近target的一个数字n, 那么用二叉搜索找即可, 设lo是0, hi是target, 那么mid就是中间假设的答案, 这个答案可以通过题意的改变数组后, 找到和target的差值, 因为我们知道mid是单调递增的, 所以可以用二叉搜索.
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;
}
}