题目

给定一个非负数组成的数组，长度一定大于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;
    }