1300. Sum of Mutated Array Closest to Target

Link

Solution

類似之前的通則

值得注意的是

1. end是arr中最大的數

2. 回傳的結果必須使Math.abs(sum-target)最小

 public int findBestValue(int[] arr, int target) {
        int N = arr.length;
        int start = 0, end = 0, total = 0;
        for(int num : arr){
            end = Math.max(end, num);
            total += num;
        }
        
        if(total <= target) return end; 
        
        
        while(start < end){
            //System.out.println("start:" + start + " end:" + end);
            int mid = start + (end-start)/2;
            total = getTotal(mid, arr);
            if(total == target) return mid;
            else if(total > target){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        return (target - getTotal(start-1, arr)) > (getTotal(start, arr) - target) ? start : start-1;
    }
    
    
    public int getTotal(int mid, int[] arr){
        int total = 0;
        for(int num : arr){
            total += num > mid ? mid : num;
        }
        return total;
    }