1521-找到最接近目标值的函数值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/07/19/change.png)

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。

请你返回 |func(arr, l, r) - target| 的最小值。

请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

示例 1：

**输入：** arr = [9,12,3,7,15], target = 5
**输出：** 2
**解释：** 所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。

示例 2：

**输入：** arr = [1000000,1000000,1000000], target = 1
**输出：** 999999
**解释：** Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。

示例 3：

**输入：** arr = [1,2,4,8,16], target = 0
**输出：** 0

提示：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
  • 0 <= target <= 10^7

思路

我们定义「按位与运算 」为题目描述中的 & 运算，「按位与之和」为若干个数依次进行 & 运算得到的值。由于：

  • 按位与运算满足交换律，即 a&b 等于 b&a；

  • 按位与运算满足结合律，即 a&b&c 等于 a&(b&c)。

所以给定的若干个数按照任意顺序进行按位与运算，得到的值都是相同的，即「按位与之和」的定义无歧义。

题目中的函数 func}(\textit{arr}, l, r) 实际上求的就是 arr}[l] 到 arr}[r] 的按位与之和，即：

\textit{arr}[l]&\textit{arr}[l+1]& \cdots &\textit{arr}[r-1]&\textit{arr}[r]

如果我们直接暴力地枚举 l 和 r，求出 func}(\textit{arr}, l, r) 的值并更新答案，那么时间复杂度至少是 O(n^2) 的（其中 n 是数组 arr 的长度）。要想通过本题，我们需要挖掘按位与之和的一些有趣的性质。

如果我们固定右端点 r，那么左端点 l 可以选择 [0, r] 这个区间内的任意整数。如果我们从大到小枚举 l，那么：

  • 按位与之和是随着 l 的减小而单调递减的。

    由于按位与运算满足结合律，所以 func}(\textit{arr}, l, r) = \textit{arr}[l]&\textit{func}(\textit{arr}, l+1, r)。并且由于按位与运算本身的性质，a&b 的值不会大于 a，也不会大于 b。因此 func}(\textit{arr}, l, r) \leq \textit{func}(\textit{arr}, l+1, r)，即按位与之和是随着 l 的减小而单调递减的。

  • 按位与之和最多只有 20 种不同的值。

    当 l=r 时，按位与之和就是 arr}[r]。随着 l 的减小，按位与之和变成 arr}[r-1]&\textit{arr}[r]，arr}[r-2]&\textit{arr}[r-1]&arr[r] 等等。由于 arr}[r] \leq 10^6 < 2^{20，那么 arr}[r] 的二进制表示中最多有 20 个 1。而每进行一次按位与运算，如果按位与之和发生了变化，那么值中有若干个 1 变成了 0。由于在按位与运算中，0 不能变回 1。因此值的变化的次数不会超过 arr}[r] 二进制表示中 1 的个数，即 func}(\textit{arr}, l, r) 的值最多只有 20 种。

算法

根据上面的分析，我们知道对于固定的右端点 r，按位与之和最多只有 20 种不同的值，因此我们可以使用一个集合维护所有的值。

我们从小到大遍历 r，并用一个集合实时地维护 func}(\textit{arr}, l, r) 的所有不同的值，集合的大小不过超过 20。当我们从 r 遍历到 r+1 时，以 r+1 为右端点的值，就是集合中的每个值和 arr}[r+1] 进行按位与运算得到的值，再加上 arr}[r+1] 本身。我们对这些新的值进行去重，就可以得到 func}(\textit{arr}, l, r+1) 对应的值的集合。

在遍历的过程中，当我们每次得到新的集合，就对集合中的每个值更新一次答案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = abs(arr[0] - target);
        vector<int> valid = {arr[0]};
        for (int num: arr) {
            vector<int> validNew = {num};
            ans = min(ans, abs(num - target));
            for (int prev: valid) {
                validNew.push_back(prev & num);
                ans = min(ans, abs((prev & num) - target));
            }
            validNew.erase(unique(validNew.begin(), validNew.end()), validNew.end());
            valid = validNew;
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int closestToTarget(int[] arr, int target) {
        int ans = Math.abs(arr[0] - target);
        List<Integer> valid = new ArrayList<Integer>();
        valid.add(arr[0]);
        for (int num : arr) {
            List<Integer> validNew = new ArrayList<Integer>();
            validNew.add(num);
            int last = num;
            ans = Math.min(ans, Math.abs(num - target));
            for (int prev : valid) {
                int curr = prev & num;
                if (curr != last) {
                    validNew.add(curr);
                    ans = Math.min(ans, Math.abs(curr - target));
                    last = curr;
                }
            }
            valid = validNew;
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = abs(arr[0] - target)
        valid = {arr[0]}
        for num in arr:
            valid = {x & num for x in valid} | {num}
            ans = min(ans, min(abs(x - target) for x in valid))
        return ans
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int closestToTarget(int* arr, int arrSize, int target) {
    int ans = abs(arr[0] - target);
    int* valid = (int*)malloc(sizeof(int) * 20);
    int num = 1;
    valid[0] = arr[0];
    for (int i = 0; i < arrSize; i++) {
        int* validNew = (int*)malloc(sizeof(int) * 20);
        int numNew = 1;
        validNew[0] = arr[i];
        ans = fmin(ans, fabs(arr[i] - target));
        for (int j = 0; j < num; j++) {
            validNew[numNew++] = valid[j] & arr[i];
            ans = fmin(ans, fabs((valid[j] & arr[i]) - target));
        }
        int add = 0;
        for (int j = 1; j < numNew; j++) {
            if (validNew[add] != validNew[j]) validNew[++add] = validNew[j];
        }
        num = add + 1;
        free(valid);
        valid = validNew;
    }
    return ans;
}

复杂度分析

  • 时间复杂度：O(n \log C)，这里的 C 是数组元素的最大范围，本题中 \log C = \log_2 10^6 \approx 20。

  • 空间复杂度：O(\log C)，记为集合中的值的最多数量。

思考

在上面的 C++ 代码中，我们使用了 unique() + erase() 进行去重操作。然而 unique() 函数必须在数组有序时才能使用。我们没有对数组进行过排序，但为什么它是正确的呢？

答案：可以使用数学归纳法。

  • 当 r=0 时，集合中只有一个值，显然是有序的；

  • 假设当 r=r_0 时有序，那么当 r=r_0+1 时，将一个有序的集合对同一个数 arr}[r_0+1] 进行按位与运算，得到的集合仍然保持有序。并且我们是在一开始就将 arr}[r_0+1] 加入了集合，它显然不小于集合中的所有数。因此最终的集合是有序的，进行去重操作后也仍然保持有序。

 Comments
On this page
1521-找到最接近目标值的函数值