2021-05-19：给定一个非负数组成的数组，长度一定大于1，想知道数组中哪两个数&的结果最大。返回这个最大结果。时间复杂度O(N)，额外空间复杂度O(1)。
福大大 答案2021-05-19：
因为是正数，所以不用考虑符号位(31位)
首先来到30位，假设剩余的数字有N个(整体)，看看这一位是1的数，有几个
如果有0个、或者1个
说明不管怎么在数组中选择，任何两个数&的结果在第30位上都不可能有1了
答案在第30位上的状态一定是0，
保留剩余的N个数，继续考察第29位，谁也不淘汰(因为谁也不行，干脆接受30位上没有1的事实)
如果有2个，
说明答案就是这两个数(直接返回答案)，因为别的数在第30位都没有1，就这两个数有。
如果有>2个，比如K个
说明答案一定只用在这K个数中去选择某两个数，因为别的数在第30位都没有1，就这K个数有。
答案在第30位上的状态一定是1，
只把这K个数作为剩余的数，继续考察第29位，其他数都淘汰掉
.....
现在来到i位，假设剩余的数字有M个，看看这一位是1的数，有几个
如果有0个、或者1个
说明不管怎么在M个数中选择，任何两个数&的结果在第i位上都不可能有1了
答案在第i位上的状态一定是0，
保留剩余的M个数，继续考察第i-1位
如果有2个，
说明答案就是这两个数(直接返回答案)，因为别的数在第i位都没有1，就这两个数有。
如果有>2个，比如K个
说明答案一定只用在这K个数中去选择某两个数，因为别的数在第i位都没有1，就这K个数有。
答案在第i位上的状态一定是1，
只把这K个数作为剩余的数，继续考察第i-1位，其他数都淘汰掉。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{1, 2, 3, 4, 5}
ret := maxAndValue2(arr)
fmt.Println(ret)
}
func maxAndValue2(arr []int) int {
// arr[0...M-1] arr[M....]
M := len(arr)
ans := 0
for bit := 62; bit >= 0; bit-- {
// arr[0...M-1] arr[M...]
i := 0
tmp := M
for i < M { // arr[0...M-1]
if (arr[i] & (1 << bit)) == 0 {
M--
arr[i], arr[M] = arr[M], arr[i]
} else {
i++
}
}
if M == 2 { // arr[0,1]
return arr[0] & arr[1]
}
if M < 2 {
M = tmp
} else { // > 2个数 bit位上有1
ans |= 1 << bit
}
}
return ans
} 执行结果如下：
京公网安备 11010502036488号