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);
}

评论