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

前言

上一篇博客 聊一聊 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);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

我们回头想一下，在上一篇博客 聊一聊 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
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
34
35
36

---

求出被去掉的两个数

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

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

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

x + y  =  m
xx + yy  =  n
1
2

这种解法只需遍历数组一次，时间复杂度为 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第二种解法

既然其他数字都出现 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];
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

相关推荐

参考博客

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

相关推荐

聊一聊 Android 中巧妙的位操作

二分查找的相关算法题

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

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