1300. Sum of Mutated Array Closest to Target

[Tcdian]

1300. Sum of Mutated Array Closest to Target

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近  target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的 最小值。

请注意，答案不一定是 arr 中的数字。

Example 1

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2

Input: arr = [2,3,5], target = 10
Output: 5

Example 3

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Note

• 1 <= arr.length <= 10^4
• 1 <= arr[i], target <= 10^5

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
    arr.sort((a, b) => a - b);
    const prefixs = new Array(arr.length);
    let prefix = 0;
    for (let i = 0; i < arr.length; i++) {
        prefix += arr[i];
        prefixs[i] = prefix;
    }
    let left = 0;
    let right = arr[arr.length - 1];
    let absoluteDifference = Infinity;
    let result = 0;
    while (left <= right) {
        const mid = (left + right) >> 1;
        const separator = sortedIndex(arr, mid);
        const prefixSum = separator > 0 ? prefixs[separator - 1] : 0;
        const sum = prefixSum + (arr.length - separator) * mid;
        if (sum < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        const abs = Math.abs(target - sum);
        if (abs < absoluteDifference) {
            absoluteDifference = abs;
            result = mid;
        } else if (abs === absoluteDifference) {
            result = Math.min(result, mid);
        }
    }
    return result;
};

function sortedIndex(arr, value) {
    const len = arr.length;
    if (value > arr[arr.length - 1]) {
        return arr.length;
    }

    let left = 0;
    let right = len - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

• TypeScript Solution

function findBestValue(arr: number[], target: number): number {
    arr.sort((a, b) => a - b);
    const prefixs: number[] = new Array(arr.length);
    let prefix = 0;
    for (let i = 0; i < arr.length; i++) {
        prefix += arr[i];
        prefixs[i] = prefix;
    }
    let left = 0;
    let right = arr[arr.length - 1];
    let absoluteDifference = Infinity;
    let result = 0;
    while (left <= right) {
        const mid = (left + right) >> 1;
        const separator = sortedIndex(arr, mid);
        const prefixSum = separator > 0 ? prefixs[separator - 1] : 0;
        const sum = prefixSum + (arr.length - separator) * mid;
        if (sum < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        const abs = Math.abs(target - sum);
        if (abs < absoluteDifference) {
            absoluteDifference = abs;
            result = mid;
        } else if (abs === absoluteDifference) {
            result = Math.min(result, mid);
        }
    }
    return result;
};

function sortedIndex(arr: number[], value: number): number {
    const len = arr.length;
    if (value > arr[arr.length - 1]) {
        return arr.length;
    }

    let left = 0;
    let right = len - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}