java 算法题 - 面试中常见的位操作算法题

喜欢ヅ旅行 2022-04-03 10:58 191阅读 0赞

## 前言 ##

上一篇博客 [聊一聊 Android 中巧妙的位操作][Android] 中，我们讲解了 java 中常用的位运算及常用应用场景，今天，让我们一起来看一下，面试中常见的位操作的算法题。

--------------------

## 两个只出现一次的数字 ##

【题目描述】一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

看到这道题目，先思考一下，你会怎么做？

不熟悉位运算性质的同学，很多人第一时间可能都有这样的想法

遍历数组，记录下数组中每个数字的出现次数，再找到那两个值出现一次的数字。

这里我们以 ArrayList 为例子，进行解答，思路大概如下

1.  遍历数组，使用一个 ArrayList 记录当前只出现了一次的值。
2.  若当前遍历的值，在 ArrayList 中已经出现，则移除该值，继续遍历。
3.  最后剩下的两个值，即为所求。

于是我们可以快速写出以下的代码。

public class Solution {
    
        public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < array.length; i++) {
                if (!list.contains(array[i]))
                    list.add(array[i]);
                else
                    list.remove(new Integer(array[i]));
            }
            if (list.size() > 1) {
                num1[0] = list.get(0);
                num2[0] = list.get(1);
            }
        }
    }

想一下，这样的时间复杂度和空间复杂度是多少呢？

我们容易得出时间复杂度为 O(n), 空间复杂度也为 O(n)。那有没有更优的解法呢？

我们回头想一下，在上一篇博客 [聊一聊 Android 中巧妙的位操作][Android] 中，我们讲到异或运算符，若位上相同，则为 0 ，位上不同，则为 1。既然数组中其他数字都能出现两次，只有两个数字出现一次，那么我们遍历数组，进行异或之后，异或之后得出的结果为这两个数（只出现一次）的异或异或结果。

为什么呢？答案很简单，两个相同的数进行异或之后，结果为 0，而任何一个数与 0 异或结果等于他本身。

得出这两个数的异或结果之后又什么用呢？想一下，异或的特征，位上相同则为 0，位上不同则为 1.由于这两个数不同，那么这两个数的异或结果肯定不为 0，即至少存在某一位为 1.

因此，我们可以找出第一位为 1 的位数，然后根据这一位是否为 1，将数组分为两组，分别进行异或，异或结束后即为我们所求的结果。

public class Solution {
        public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)    {
            int length = array.length;
            if(length == 2){
                num1[0] = array[0];
                num2[0] = array[1];
                return;
            }
            int bitResult = 0;
            for(int i = 0; i < length; ++i){
                bitResult ^= array[i];
            }
            int index = findFirst1(bitResult);
            for(int i = 0; i < length; ++i){
                if(isBit1(array[i], index)){
                    num1[0] ^= array[i];
                }else{
                    num2[0] ^= array[i];
                }
            }
        }
    
        private int findFirst1(int bitResult){
            int index = 0;
            while(((bitResult & 1) == 0) && index < 32){
                bitResult >>= 1;
                index++;
            }
            return index;
        }
    
        private boolean isBit1(int target, int index){
            return ((target >> index) & 1) == 1;
        }
    }

--------------------

## 求出被去掉的两个数 ##

**\[题目描述\] 给你1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。**

*  第一种方法:使用方程组进行解决

遍历被打乱的数组时，计算value的累加值和value平方的累加值。结合未打乱之前的数组，这样就能得出 x + y = m 与 xx + yy = n两个方程，解这组方程即可算出被去掉的两个数。这种方法比较容易理解，实现起来也比较简单

x + y  =  m
    xx + yy  =  n

这种解法只需遍历数组一次，时间复杂度为 O(n)

*  第二种解法：使用异或解决

解法基本跟上面的题目一样，这里说一下思路.

*  将这个数组与 0-1000 这 n 个连续自然数进行异或，得到这两个去掉的数的异或值
 *  再找出这个异或值第 1 位为 1 的位数，标记为 N
 *  在遍历这个数组，根据第 N 位是否为 1，分为两组进行异或

这种解法需要遍历数组两次，时间复杂度为 O(n)

--------------------

## 在其他数都出现三次的数组中找到只出现一次的数 ##

出现三次或者三次以上去找那个单独的值的时候该怎么办呢？好像不能用异或了，但是考虑到输入是 int 型数组，所以可以用32位来表达输入数组的元素。

假设输入中没有 single number，那么输入中的每个数字都重复出现了数字，也就是说，对这 32 位中的每一位i而言，所有的输入加起来之后，第 i 位一定是 3 的倍数。

现在增加了single number，那么对这 32 位中的每一位做相同的处理，也就是说，逐位把所有的输入加起来，并且看看第 i 位的和除以 3 的余数，这个余数就是 single number 在第 i 位的取值。这样就得到了 single  
number 在第i位的取值。这等价于一个模拟的二进制，接着只需要把这个模拟的二进制转化为十进制输出即可。

另外，这个做法可以扩展，如果有一堆输入，其中 1 个数字出现了 1 次，剩下的数字出现了 K 次，这样的问题全部可以使用这样的办法来做。

### 在其他数都出现k次的数组中找到只出现一次的数 ###

public class SingleNum {
        public static void main(String[] args) {
    		SingleNum s=new SingleNum();
    		int[] arr= {2,2,2,5,2,3,4,5,4,5,4,5,4};
    		System.out.println(s.singleNumber(arr,4));
    	}
    	
        public static int singleNumber(int A[],int k) {  
            int n=A.length;
            int[] count=new int[32];  
            int result=0;  
            for(int i=0;i<32;i++){  
                for(int j=0;j<n;j++){  
                	count[i]+=((A[j]>>i)&1);
                	//首先把输入数字的第i位加起来,这里和1去与，取到的就是一位
                }  
                count[i]=count[i]%k; 
                  //然后求它们除以k的余数
                result|=(count[i]<<i);//把二进制表示的结果转化为十进制表示的结果  
            }  
            return result;
        }
    }

### 第二种解法 ###

既然其他数字都出现 n 次 （n > 1)，只有一个数字出现 1 次, 那么我们可以先对数组进行排序，接着去遍历数组，对于中间的数字考虑是否前后有相同的，对于第一数字单独处理

import java.util.*;
     
    public class Solution { 
        public int singleNumber(int[] A) { 
            int i=0;
            Arrays.sort(A);
            for(i=0;i<A.length-1;i++){ 
                if(i==0){ 
                    if(A[i]==A[i+1]){ continue;}
                }else{ 
                    if(A[i]==A[i+1]||A[i]==A[i-1]){ 
                    continue;
                     }
                }
                break;
            }
            return A[i];
        }

--------------------

## 相关推荐 ##

### 参考博客 ###

[在每个数字都出现K次的数组中，找只出现一次的数][K]

### 相关推荐 ###

[聊一聊 Android 中巧妙的位操作][Android]

[二分查找的相关算法题][Link 1]

[快速排序的相关算法题（java）][java]

最后的最后，卖一下广告，欢迎大家关注我的微信公众号，扫一扫下方二维码或搜索微信号 Android 技术人，即可关注。 目前专注于 Android 开发，主要分享 Android开发相关知识和一些相关的优秀文章，包括个人总结，职场经验等。  
![20181225102727672][]

[Android]: https://blog.csdn.net/gdutxiaoxu/article/details/84898590
[K]: https://blog.csdn.net/weixin_30363263/article/details/80198527
[Link 1]: https://blog.csdn.net/gdutxiaoxu/article/details/51292440
[java]: https://blog.csdn.net/gdutxiaoxu/article/details/51299994
[20181225102727672]: /images/20220403/8a11f271f0704ff786da68a91ec4ab00.png