java 算法题 - 面试中常见的位操作算法题
前言
上一篇博客 聊一聊 Android 中巧妙的位操作 中，我们讲解了 java 中常用的位运算及常用应用场景，今天，让我们一起来看一下，面试中常见的位操作的算法题。
两个只出现一次的数字
【题目描述】一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
看到这道题目，先思考一下，你会怎么做？
不熟悉位运算性质的同学，很多人第一时间可能都有这样的想法
遍历数组，记录下数组中每个数字的出现次数，再找到那两个值出现一次的数字。
这里我们以 ArrayList 为例子，进行解答，思路大概如下
- 遍历数组，使用一个 ArrayList 记录当前只出现了一次的值。
- 若当前遍历的值，在 ArrayList 中已经出现，则移除该值，继续遍历。
- 最后剩下的两个值，即为所求。
于是我们可以快速写出以下的代码。
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 中巧妙的位操作 中，我们讲到异或运算符，若位上相同，则为 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 numer在第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];
}相关推荐
参考博客
相关推荐