leetcode 1521

问题

img

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

1
2
3
Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [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 got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

1
2
3
Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

1
2
Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

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

分析

解1: 在不考虑数据集范围的情况下，直观的解法是 $O(n^2)$ 。在这个基础上稍微增加一点优化就能通过。（应该是数据集的设计不太严谨有漏网之鱼。）。优化1: 从arr[i] 开始向后做 & 运算，结果会越来越小，如果小于 target，就返回。优化2: 如果在运算过程中发现和 target 相差为0，则直接 return 0;。 优化3: 如果在从arr[i] 开始一直到 arr[n-1] 相与的结果大于 target，那么以arr[j] (j > i) 开始的所有与的结果都会大于 “arr[i] 开始一直到 arr[n-1] 相与的结果” 且大于 target，所以直接跳出循环。三个优化缺一不可。

解2: 利用位操作 与 运算的特点，越“与”越小，“与”下来只会让之前的数的某位1变为0。因此 {a[0], a[0]&a[1], a[0]&a[1]&a[2], … ,a[0]&a[1]&…&a[i]} 最多有32个不重复的数。因此，可以使用 unordered_set 来进行解，最终的时间复杂度会是 $O(32N)$，也就是 $O(N)$。

寻找线段树的解法… 再看看讨论区（暂时还没有找到合适的线段树的解法）

解3: 自己的线段树代码，时间复杂度分析是 $O(NlogNlogN)$，但是 TLE。

答案1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {  // 376ms
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = INT_MAX;
        for (int i = 0; i < arr.size(); ++i) {
            int sum = arr[i];
            for (int j = i; j < arr.size(); ++j) {
                sum &= arr[j];
                ans = min(ans, abs(target-sum));
                if (sum == target) return 0;
                if (sum < target) break;
            }
            if (sum > target) break;  // 重点且难以想到
        }
        return ans;
    }
};

答案2

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
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {  // 1940 ms 在过与不过的边缘
public:
    int closestToTarget(vector<int>& arr, int target) {
        unordered_set<int> st;
        int ans = INT_MAX;
        for (int i = 0; i < arr.size(); ++i) {
            unordered_set<int> st2;
            for (auto it: st) {
                st2.insert(it&arr[i]);
            }
            st2.insert(arr[i]);
            for (auto it: st2) {
                ans = min(ans, abs(it - target));
            }
            st = st2;
        }
        return ans;
    }
};

class Solution {  // 1576 ms 采用set竟然比使用 unordered_set 所用的时间还短
public:
    int closestToTarget(vector<int>& arr, int t)
	{
		set<int> s1;
		int ans=INT_MAX;
		int n=arr.size();
		for(int i=0;i<n;i++)
		{
			set<int> s2;
			s2.insert(arr[i]);
			for(auto a:s1)
			{
				s2.insert(arr[i]&a);
			}
			for(auto a:s2)
			{
				ans=min(ans,abs(a-t));
			}
			s1=s2;
		}
		return ans;
	}
};

答案3

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {  // TLE
public:
    struct segmentTree {
        int l, r;
        int dat;
    } t[400010];
    
    void build(vector<int>& arr, int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) {
            t[p].dat = arr[l-1];
            return;
        }
        int mid = l + (r-l)/2;
        build(arr, 2*p, l, mid);
        build(arr, 2*p + 1, mid+1, r);
        t[p].dat = t[2*p].dat & t[2*p+1].dat;
    }
    
    int ask(int p, int l, int r) {
        if (l <= t[p].l && r >= t[p].r)
            return t[p].dat;
        
        int mid = t[p].l + (t[p].r - t[p].l)/2;
        int val = 0x1fffffff;
        if (l <= mid) val &= ask(2*p, l, r);
        if (r > mid) val &= ask(2*p+1, l, r);
        return val;
    }

    int closestToTarget(vector<int>& arr, int target) {
        int n = arr.size();
        build(arr, 1, 1, n);
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            int lo = i, hi = n;
            while (lo <= hi) {
                int mi = lo + (hi-lo)/2;
                int val = ask(1, i, mi);
                if (val > target) {
                    lo = mi + 1;
                } else {
                    hi = mi - 1;
                }
            }
            int tmp = INT_MAX;
            if (lo <= n) tmp = min(abs(ask(1, i, lo)-target), tmp);
            if (lo-1 >= i) tmp = min(abs(ask(1, i, lo-1)-target), tmp);
            ans = min(tmp, ans);
        }
        return ans;
    }
};