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