1300. 转变数组后最接近目标值的数组和¶

难度：中等

题目¶

给你一个整数数组 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

Reference

题解¶

在待查区间 $(lo, hi)$ 中确定三等分点 $x_1, x_2 (x_1 < x_2)$ ，分别计算两个三等分点处的差值。设 $f(x)$ 为将数组中大于 $x$ 的数值转变为 $x$ 后数组求和与目标值之差的绝对值。

当 $f(x_1) < f(x_2)$ 时，将待查区间缩减为 $(lo, x_2)$
当 $f(x_1) > f(x_2)$ 时，将待查区间缩减为 $(x_1, hi)$

$f(x)$ 可以通过二分查找+预处理在 $\mathcal O(\log N)$ 的时间内计算完成。预处理需要花费 $\mathcal O(N)$ 的时间。排序需要花费 $\mathcal O(N\log N)$ 的时间。需要 $\mathcal O(\log N)$ 次三分查找。因此总的时间复杂度为 $\mathcal O(N\log N)$ （预处理阶段）

#define ABS(x) ((x) > 0 ? (x) : -(x))

int cmp(const void *a, const void *b)
{
    return *((int *)a) - *((int *)b);
}

int bSearch(int *arr, int target, int lo, int hi)
{
    int mid;
    while (lo < hi)
    {
        mid = (lo + hi) >> 1;
        if (arr[mid] < target)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo - 1;
}

int test(int *arr, int arrSize, int target, int val, int *presum)
{
    int i = bSearch(arr, val, 0, arrSize), ret = val * (arrSize - i - 1) - target;
    if (i >= 0)
        ret += presum[i];
    return ABS(ret);
}

int tSearch(int *arr, int arrSize, int target, int lo, int hi, int *presum)
{
    int left, right;
    while (hi - lo > 2)
    {
        left = (2 * lo + hi) / 3;
        right = (2 * hi + lo) / 3;
        if (test(arr, arrSize, target, left, presum) <= test(arr, arrSize, target, right, presum))
            hi = right;
        else
            lo = left;
    }
    return (2 * hi + lo) / 3;
}

int findBestValue(int* arr, int arrSize, int target){
    int i = 0, presum[arrSize];
    qsort(arr, arrSize, sizeof(int), cmp);
    presum[0] = arr[0];
    for (i = 1; i < arrSize; i++)
        presum[i] = presum[i - 1] + arr[i];

    return tSearch(arr, arrSize, target, -1, arr[arrSize - 1] + 1, presum);
}

1300. 转变数组后最接近目标值的数组和¶

题目¶

题解¶

评论