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

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，1300. Sum of Mutated Array Closest to Target

先看题目描述

qi

题目大意就是给定一个整数数组 arr 和一个目标值 target ，返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target

算法和思路

算法流程qi

  • 先对数组排序并求出数组和，若数组和小于 target，直接返回排序后数组的最后一项

  • 若数组和大于 target，则先令 value = target / len，然后计算得到将数组中所有大于 value 的值变成 value 后，数组和与 target 之差的绝对值 dif，然后执行循环

    • 令 value = value+ 1，prevDif = dif，计算得到将数组中所有大于 value 的值变成 value 后，数组和与 target 之差的绝对值 dif

    • 重复上述步骤直到 prevDif <= dif，退出循环

  • 返回 value - 1

解释：如果我们以 value 为自变量，将数组中所有大于 value 的值变成 value 后数组之和 F(value)看作因变量，那么 F(value) 就是一个关于 value 的函数，再令 G(value) = F(value) - target 的绝对值，经分析后我们可以得出一个结论，F(value) 是关于 value 的单调递增函数，则G(value) 在整数域上是关于 value的先递减再递增函数，因为F(value) 一定是小于等于 value * len 的，故在 [target / len, +∞) 中一定存在一个 value 值，使得 G(value) 取得最小值，因此我们结合 G(value) 的单调性分析可以得到，当 G(value) < G(value + 1)时，这个 value 就是题目要求的值

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Arrays;

class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int len = arr.length;
        int[] prefix = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
        if (prefix[len] <= target) return arr[len - 1];
        int value = target / len;
        int border = 0;
        for (int i = 0; i < len; i++) {
            if (arr[i] >= value) {
                border = i;
                break;
            }
        }
        int cur = prefix[border] + value * (len - border);
        int dif = Math.abs(cur - target);
        int prevDif;
        do {
            prevDif = dif;
            value++;
            while (arr[border] < value) border++;
            cur = cur + len - border;
            dif = Math.abs(cur-target);
        } while (dif < prevDif);
        return value - 1;
    }
}