---

题目

给定一个非负数组成的数组，长度一定大于1
想知道数组中哪两个数&的结果最大
返回这个最大结果

时间复杂度O(N)，额外空间复杂度O(1)

一、解题思路

可以用前缀树,额外空间比较大,
存在更好的解法思路:高位尽量变1因为我如果选一些数让30位变成0,它就不如30位变成1的值大。
先遍历一遍所有的数字,只考察30位是1的有几个,分情况

1)小于两个
这说明最终的结果30位上肯定不是1,因为你小于两个就不存在任何两个数与完之后第30位是1
2)正好有两个数,就是这两个数与完的结果最大,直接返回就行

3)大于两个数
那我就把这100个数淘汰掉,剩下的我只留这23个数,我再去看第29位

解题步骤

第i位上有1的数:

1. <2个
2. =2个
   3)>2个
   我们遍历一遍整个数组，如果有第i位上有1的数,第1种情况小于两个,那么这20个数一个也不淘汰,你接下来去看i-i位。
   第2种情况如果这20个数中第1位上1的只有两个数,你不用再看,直接返回
   第3种情况如果在第i位上有1的数是大于两个的,比如说他有7个,删掉剩余的13个,只留这7个数去搞下一位

我们设置一个垃圾区,即淘汰的数,

如果是第三种情况,在遍历数组中,只用遍历垃圾区前的数就行了

代码

	public static int maxAndValue2(int[] arr) {
		// arr[0...M-1]  arr[M....]
		int M = arr.length;
		int ans = 0;
		for (int bit = 30; bit >= 0; bit--) {
			// arr[0...M-1] arr[M...]
			int i = 0;
			int tmp = M;
			while (i < M) { //遍历垃圾区前的数
				//如果i位为1,与垃圾区前一个数交换,垃圾区往左扩
				if ((arr[i] & (1 << bit)) == 0) {
					swap(arr, i, --M);
				} else {
					i++;
				}
			}
			if (M == 2) { 
				return arr[0] & arr[1];
			}
			if (M < 2) {
				M = tmp;
			} else { //m>2的情况
				ans |= (1 << bit);
			}
		}
		return ans;
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
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