非负数组中两个数相与的最大结果：互为倒数的两个数加起来的最小值

本文主要介绍关于算法,数据结构,排序算法的知识点，对【非负数组中两个数相与的最大结果】和【互为倒数的两个数加起来的最小值】有兴趣的朋友可以看下由【小卢要刷力扣题】投稿的技术文章，希望该技术和经验能帮到你解决你所遇的相关技术问题。

互为倒数的两个数加起来的最小值

文章目录 题目一、解题思路解题步骤 代码

---

题目

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

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

一、解题思路

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

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

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

解题步骤

第i位上有1的数:

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

本文《非负数组中两个数相与的最大结果》版权归小卢要刷力扣题所有，引用非负数组中两个数相与的最大结果需遵循CC 4.0 BY-SA版权协议。