文档章节

剑指Offer(Java版):数组出现一次的数字

一贱书生
 一贱书生
发布于 2016/08/03 15:11
字数 1969
阅读 20
收藏 0

题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。

 * 请些程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)

例如输入数组{2,4,3,6,3,2,5,5},因为只有4,6这两个数字只出现一次,其他数字都出现了两次,所以输出4,6

这是一个比较难的题目,很少有人在面试的时候不需要提示一下子想到最好的解决办法。一般当应聘者想了几分钟那个后还没有思路,面试官会给出一些提示。

我们想到异或运算的一个性质:任何一个数字异或它自己都等于0,也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是哪个出现一次的数字,因为那些成对出现的两次的数字都在异或中低消了。

我们试着把数组分成两个子数组,使得每个子数组只包含一次出现一次的数字,而其他数字都成对出现两次。如果能够这样拆分成两个数组,我们就可以按照前面的办法分别找出两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就 是两个只出现一次的数字的异或的结果。因为其他数字都出现两次,在异或中全部抵消了。由于这两个数字肯定不一样,那么异或的结果肯定不为0,也就是说在这 个结果数字的二进制表示中至少有一位为1.我们在结果数字中找到第一个为1的位的位置,记为第n位。现在我们以第n位是不是1为标准把原数组中的数字分成 两个子数组,第一个子数组中的每个数字的第n位都是1,而第二个子数组中每个数字的第n位都为0.由于我们分组的标准是数字中的某一位是1还是0,那么出 现了两次的数字肯定被分配到同一个子数组中。因为两个相同的数字的任意一位都是相同的,我们不可能把两个相同的数字分配到两个子数组中去,于是我们已经把 原数组分成了两个子数组,每个子数组都包含了一个只出现一次的数字,而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次的数字,因 此到此位置所有的问题都解决了。

举个例子,加入我们输入的数字是 {2,4,3,6,3,2,5,5}。当我们依次对数组中的每一个数字做异或运算之后,得到的结果用二进制表示为0010.异或得到的结果中的倒数第二位 是1,于是我们根据数字的倒数第二位是不是1分为两个数组。第一个子数组{2,3,6,3,2}中所有的数字倒数第二位都是1,而第二个子数组 {4,5,5}中所有的数字的倒数第2位都是0,接下来只要分别对这两个子数组求异或,就能找出第一个子数组中只出现一次的数字是6,而第二个子数组只出 现一次的数字是4.

Java实现的代码如下:

package cglib;

public class jiekou {
       public void findNumsAppearOnce(int[] arr){  
            if(arr == null)  
                return;  
            int number = 0;  
            for(int i: arr)  
            {   
                System.out.println("number="+number);
                System.out.println("i="+i);
                number^=i;
                System.out.println("与i异或后:number="+number);
            }
            int index = findFirstBitIs1(number);  
            int number1= 0,number2 = 0;  
            for(int i : arr){  
                if(isBit1(i,index))  
                    number1^=i;  
                else  
                    number2^=i;  
            }  
            System.out.println(number1);  
            System.out.println(number2);  
        }  
        private int findFirstBitIs1(int number){
            System.out.println("findFirstBitIs1:number="+number);
            int indexBit = 0;  
            System.out.println("findFirstBitIs1:indexBit="+indexBit);
            while((number & 1)== 0){
                 System.out.println("findFirstBitIs1:number & 1=0");
                number = number >> 1;
                System.out.println("findFirstBitIs1:number>> 1="+number);
                ++indexBit;
                System.out.println("findFirstBitIs1:++indexBit="+indexBit);
            }  
            return indexBit;  
        }  
        private boolean isBit1(int number,int index){
            System.out.println("isBit1:number="+number);
            System.out.println("isBit1:index="+index);
            number = number >>index;
            
            System.out.println("isBit1:number >>index="+number);
            return (number & 1) == 0;  
        }  
        public static void main(String[] args){  
            int[] arr={6,2,4,3,3,2,5,5};  
            jiekou test = new jiekou();  
            test.findNumsAppearOnce(arr);  
        }
    }
   

 

输出:

number=0
i=6
与i异或后:number=6
number=6
i=2
与i异或后:number=4
number=4
i=4
与i异或后:number=0
number=0
i=3
与i异或后:number=3
number=3
i=3
与i异或后:number=0
number=0
i=2
与i异或后:number=2
number=2
i=5
与i异或后:number=7
number=7
i=5
与i异或后:number=2
findFirstBitIs1:number=2
findFirstBitIs1:indexBit=0
findFirstBitIs1:number & 1=0
findFirstBitIs1:number>> 1=1
findFirstBitIs1:++indexBit=1
isBit1:number=6
isBit1:index=1
isBit1:number >>index=3
isBit1:number=2
isBit1:index=1
isBit1:number >>index=1
isBit1:number=4
isBit1:index=1
isBit1:number >>index=2
isBit1:number=3
isBit1:index=1
isBit1:number >>index=1
isBit1:number=3
isBit1:index=1
isBit1:number >>index=1
isBit1:number=2
isBit1:index=1
isBit1:number >>index=1
isBit1:number=5
isBit1:index=1
isBit1:number >>index=2
isBit1:number=5
isBit1:index=1
isBit1:number >>index=2
4
6

 

 

拓展:

package cglib;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class jiekou {
/**
 *  如果数组中没有x,那么数组中所有的数字都出现了3次,在二进制上,每位上1的个数肯定也能被3整除。如{1, 5, 1, 5, 1, 5}从二进制上看有:

1:0001

5:0101

1:0001

5:0101

1:0001

5:0101

二进制第0位上有6个1,第2位上有3个1.第1位和第3位上都是0个1,每一位上的统计结果都可以被3整除。而再对该数组添加任何一个数,如果这个数在二进制的某位上为1都将导致该位上1的个数不能被3整除。因此通过统计二进制上每位1的个数就可以推断出x在该位置上是0还是1了,这样就能计算出x了。

推广一下,所有其他数字出现N(N>=2)次,而一个数字出现1次都可以用这种解法来推导出这个出现1次的数字。
 *
 *
 */
    
/**
     * 数组a中只有一个数出现一次,其他数都出现了2次,找出这个数字
     * @param a
     * @return
     */
    public static int find1From2(int[] a){
        int len = a.length, res = 0;
        for(int i = 0; i < len; i++){
            res = res ^ a[i];
        }
        return res;
    }
/**
     * 数组a中只有一个数出现一次,其他数字都出现了3次,找出这个数字
     * @param a
     * @return
     */
    public static int find1From3(int[] a){
        int[] bits = new int[32];
        int len = a.length;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < 32; j++){
                bits[j] = bits[j] + ( (a[i]>>>j) & 1);
            }
        }
        int res = 0;
        for(int i = 0; i < 32; i++){
            if(bits[i] % 3 !=0){
                res = res | (1 << i);
            }
        }
        return res;
    }
   
    
    /**
     * 数组a中只有一个数出现2次,其他数字都出现了4次,找出这个数字
     * @param a
     * @return
     */
    public static void find1From6(int[] a){
        
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<a.length;i++){
            Integer num=map.get(a[i]);
            if(num!=null){
                map.put(a[i],++num);
            }else{
                map.put(a[i],1);
            }
        }
        int n=2; //设置输出指定次数的值
        Iterator<Entry<Integer,Integer>> ite=map.entrySet().iterator();
        while(ite.hasNext()){
            Entry<Integer,Integer> entry=ite.next();
            if(entry.getValue() == n){
                System.out.println("出现次数为"+n+"次的数字有:"+entry.getKey());
            }
        
    }
        
    }
    /**
     * 数组a中只有一个数出现一次,其他数字都出现了5次,找出这个数字
     * @param a
     * @return
     */
    
    public static int find1From5(int[] a){
        int[] bits = new int[32];
        int len = a.length;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < 32; j++){
                bits[j] = bits[j] + ( (a[i]>>>j) & 1);
            }
        }
        int res = 0;
        for(int i = 0; i < 32; i++){
            if(bits[i] % 5 !=0){
                res = res | (1 << i);
            }
        }
        return res;
    }
    
        public static void main(String[] args){  
            
            int[] arr2={6,2,2,3,3,4,4};
            int[] arr3={2,4,4,4,3,3,3};
            int[] arr5={8,2,2,2,2,2,4,4,4,4,4};
            int[] arr6={1,1,1,1,2,2,3,3,3,3,4,4};
            
            System.out.println(find1From2(arr2));
            System.out.println(find1From3(arr3));
            System.out.println(find1From5(arr5));
            find1From6(arr6);
            
        }
    }
   

输出:
6
2
8
出现次数为2次的数字有:2
出现次数为2次的数字有:4

 

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
剑指offer:2.二维数组的查找(Java版)

备注:本文参照《剑指offer第二版》 题目: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数, 输入这样的一个二维数组和一个整...

Tom-shushu
2018/07/28
0
0
剑指offer之数组中出现的次数

题目 一个整型数组里面除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(N),空间复杂度是O(1)。 2. 思路 首先,可以想一下,如果数组中只有一...

firepation
2018/10/10
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
剑指offer之找出数组中重复数字

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011068702/article/details/85967756 1 问题 给的N个数字的数组,每个元素的大小范围大于等于0小于N(0 << a[...

chenyu_insist
01/07
0
0
剑指Offer_4_二维数组中的查找

题目描述 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 ...

奶berber
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java8

package com.shi.lambda;import java.util.Arrays;import java.util.List;import org.junit.Test;import com.shi.model.Employee;/** * 初始化案例 * @author xiaosh......

小小小施爷
30分钟前
1
0
c# 动态编译代码

有时候做计算一些东西时候,算法一直变更,写在程序需要一直调整,因此算法写在cs文件,然后动态调用内部的方法去计算判断,只需变更cs文件即可。 using Microsoft.CSharp; using System; us...

朝如青丝暮成雪
31分钟前
3
0
好程序员技术分享html5和JavaScript的区别

好程序员技术分享html5和JavaScript的区别,HTML5广义上讲是前端开发学科的代名词,包含HTML5、CSS3及JavaScript三个重要的部分,是运行在浏览器上应用的统称。如PC端网站、管理系统、手机网...

好程序员IT
33分钟前
2
0
tomcat 与 spring boot 设置虚拟路径

tomcat 设置虚拟路径 <Context path="/uploadDir" docBase="/data"/>path是请求访问的路径docBase是服务器存储文件的路径,Linux 根目录下 data spring boot 虚拟路径设置 registry.addRe......

kdy1994
36分钟前
1
0
var ,let ,const 的区别和共同点

一、let和var区别 1.关于变量提升,var能变量提升,let不能 // 关于var 如下所示console.log(a); //输出undefined,此时就是变量提升var a = 2; console.log(a); //2 //相当于下面...

MrBoyce
41分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部