首页 > 代码库 > int类型数组中找出现几次的数的题目总结

int类型数组中找出现几次的数的题目总结

1.     题目1:int类型数组中除了一个数出现一次以外,其他数都出现两次,求该数。

【分析】全部异或运算即可。

2.     题目2:int类型数组中除了两个数出现一次以外,其他数都出现两次,求这两个数。

参考:http://zhedahht.blog.163.com/blog/static/2541117420071128950682/

【分析】:全部亦或之后得到的数为resultExclusiveOR,找到它的第一个不是0的位,然后将数组按这个位是否为0分成两组,组内全部亦或即可。

/**
 * 创建时间:2014年9月6日下午7:51:17 项目名称:Test
 *
 * @author Cao Yanfeng
 * @since JDK 1.6.0_21 类说明:数组只有两个数是只出现一次,其他的都出现两次,中找到只出现一次的两个数
 */
public classFindNumsAppearOnceTest {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array = { 1, 2, 1, 9, 3, 2,0, 3 };
        printNumsAppearOnce(array);
 
    }
 
    /* 算法思想:全部亦或之后得到的数为resultExclusiveOR,找到它的第一个不是0的位,让后将数组按这个位是否为0分成两组,组内全部亦或即可 */
    public static void printNumsAppearOnce(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int resultExclusiveOR= 0;
        for (int i = 0; i < array.length; i++) {
            resultExclusiveOR^= array[i];
        }
        int mask =1;
        /*只要相&等于0,就左移一位,直到获得模版*/
        while ((resultExclusiveOR&mask)==0) {
            mask<<=1;  
        }
        int result1 = 0, result2 = 0;
        for (int i = 0; i < array.length; i++) {
            if ((array[i]&mask)== 0) {
                result1 ^= array[i];
            }else{
                result2 ^= array[i];
            }
        }
        System.out.println("这两个数分别是" + result1 + ","+ result2);
    }
}


3.     题目3:int类型数组中除了三个数出现一次以外,其他数都出现两次,求这三个数

题目的另一种简单形式:求这三个数中任意一个数。

参考:http://zhedahht.blog.163.com/blog/static/25411174201283084246412/

【分析】以实际例子说明:数组为array,三个数互不相同,比如是001,010,100

1)  第一次遍历获得这三个数的异或X=a^b^c,即X=111,可以证明X与a、b、c均不相同;

2)  X^a=b^c=110,X^b=a^c=101,X^c=a^b=011,可以证明这三个数也均不相同。定义函数f(X^a)= f(b^c)=010表示保留除了最后一个bit位为1的位置外其它bit位全部置为0,则f(X^b)= 001,f(X^c)= 001。第二次遍历获取f(X^a)^f(X^b)^f(X^c)的结果即f(X^a)^f(X^b)^f(X^c)=010。

3)  获取f{f(X^a)^f(X^b)^f(X^c)}的结果f{f(X^a)^f(X^b)^f(X^c)}=010,即保留除了最后一个bit位为1的位置外,其它bit位全部置为0,注意,这里获取了一个模版,f(X^a)、f(X^b)、f(X^c)即010、001、001三个数只有f(X^a)该bit位为1。

4)  第三次遍历,只要符合f(X^array[i])=010的数都全部异或,就能求出来a。

5)  第四次遍历,找到a与数组最后一个数交换,0~array.lenth-2范围内可以求得另外两个数。

/** 
 * 创建时间:2014年9月6日下午9:36:17 
 * 项目名称:Test 
 * @authorCao Yanfeng 
 * @sinceJDK 1.6.0_21 
 * 类说明:   数组只有三个数是只出现一次,其他的都出现两次,中找到只出现一次的三个数
 * 至少需要5次遍历,其中一次是处理将第一个找到的元素删除或再添加一个进去,这里是通过将它与最后一个元素交换来删除的。
 */
public class FindThreeUniqueTest {
 
         /**
          * @paramargs
          */
         public static void main(String[] args) {
                   // TODO Auto-generated method stub
                   int[] array={2,3,3,4,5,5,0};
                   printThreeUnique(array);
 
         }
         public static void printThreeUnique(int[] array) {
                   if (array==null||array.length<3) {
                            return;
                   }
                   /*第一次遍历,找到三个数的亦或X*/
                    int xorResult =0;
                    for (int i = 0; i < array.length; i++) {
                            xorResult^=array[i];
                   }
                    /*第二次遍历,找到f(X^a)^f(X^b)^f(X^c)的结果*/
                    int index=0;
                    for (int i = 0; i < array.length; i++) {
                            index^=lastBitof1(xorResult^array[i]);
                   }
                    /*f(X^a)^f(X^b)^f(X^c)的结果只保留最后一位1,其它都置为0,假设该位为m位且f(X^a)的m位为1*/
                    index=lastBitof1(index);
                    /*第三次遍历,a一定在符合f(X^a)的m位为1的分组*/
                    int first=0;
                    for (int i = 0; i < array.length; i++) {
                            if (lastBitof1(xorResult^array[i])==index) {
                                     first^=array[i];
                            }
                   }
                    System.out.println("第一个数是:"+first);
                    /*第四次遍历,找到a的位置并跟最后一个数交换*/
                    for (int i = 0; i < array.length; i++) {
                            if (array[i]==first) {
                                     array[i]^=array[array.length-1];
                                     array[array.length-1]^=array[i];
                                     array[i]^=array[array.length-1];
                            }
                   }
                    /*在0~array.length-2范围内找两个数*/
                    printNumsAppearOnce(array, array.length-1);
         }
         public static void printNumsAppearOnce(int[] array,int lenght) {
                   if (array == null || lenght < 2) {
                            return;
                   }
                   int resultExclusiveOR = 0;
                   for (int i = 0; i < lenght; i++) {
                            resultExclusiveOR ^= array[i];
                   }
                   int mask =1;
                   /*只要相&等于0,就左移一位,直到获得模版*/
                   while ((resultExclusiveOR&mask)==0) {
                            mask<<=1;      
                   }
                   int result1 = 0, result2 = 0;
                   for (int i = 0; i < lenght; i++) {
                            if ((array[i]&mask)== 0) {
                                     result1 ^= array[i];
                            } else {
                                     result2 ^= array[i];
                            }
                   }
                   System.out.println("第二个数和第三个数分别是:" + result1 + "," + result2);
         }
         /*只保留最后一位1,其它位都置为0*/
         public static int lastBitof1(int arg){
                   return arg&~(arg-1);
         }
 
}


4.     题目4:int类型数组中除了一个数出现一次或两次以外,其他数都出现三次,求这个数。

参考:http://blog.csdn.net/dinosoft/article/details/6443354

【分析】每一个bit位,只要出现三次就将该bit位清零。

分析下面的一段代码:

/** 
 * 创建时间:2014年9月6日下午10:25:21 
 * 项目名称:Test 
 * @author Cao Yanfeng 
 * @since JDK 1.6.0_21 
 * 类说明:  int类型数组中除了一个数出现两次以外,其他数都出现三次,求这个数.
 */
public classFindDoubleTest {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array1={1,1,1,20};
        printDouble(array1,1);
        int[] array2={1,1,1,20,20};
        printDouble(array2,2);
 
    }
   
    public static void printDouble(int[] array,int oneOrTwo) {
        int ones=0,twos=0;
        for (int i = 0; i < array.length; i++) {
            twos|=ones&array[i];
            ones^=array[i];
            int not_threes=~(ones&twos);
            ones&=not_threes;
            twos&=not_threes;
        }
        switch (oneOrTwo) {
        case 1:
            System.out.println("出现1次的数为:"+ones);
            break;
        case 2:
            System.out.println("出现2次的数为:"+twos);
            break;
        default:
            break;
        }
    }
 
}


如果数组前三项都是相同的数a,箭头前是执行ones&=not_threestwos&=not_threes之前的数,箭头后是执行ones&=not_threestwos&=not_threes之后的数

i=0

i=1

i=2

twos=0→0

twos=a→a

twos=a→0

ones=a→a

ones=0→0

ones=a→0

not_threes=1

not_threes=1

not_threes=~a

 

  据此可以分析出,当a出现一次的时候,ones能保存a。当a出现两次的时候,twos能保存a。当a出现三次的时候,ones和twos都清零。所以,如果一个数值中所有的数都通过这个循环的话,出现三次的数都清零了,有一个数如果出现一次,它保存在ones中;如果出现两次的话保存在twos中。 

 

int类型数组中找出现几次的数的题目总结