leetcode-1521-Find a Value of a Mysterious Function Closest to Target
问题
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 | Input: arr = [9,12,3,7,15], target = 5 |
Example 2:
1 | Input: arr = [1000000,1000000,1000000], target = 1 |
Example 3:
1 | Input: arr = [1,2,4,8,16], target = 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 | class Solution { // 376ms |
答案2
1 | class Solution { // 1940 ms 在过与不过的边缘 |
答案3
1 | class Solution { // TLE |
Author: Hatton.Liu
Link: http://hattonl.github.io/2020/07/20/leetcode-1521/
License: 知识共享署名-非商业性使用 4.0 国际许可协议