美文网首页程序员
剑指offer----数组中只出现一次的数

剑指offer----数组中只出现一次的数

作者: qming_c | 来源:发表于2018-02-09 00:51 被阅读0次

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

    //num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    public class Solution {
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
            if(array.length < 2){
                return;
            }
            int n = 0;
            for(int i = 0; i < array.length; i++){
                n ^= array[i]; 
            }
            int last = n - ((n - 1) & n);
            for(int i = 0; i < array.length; i++){
                if( ( last & array[i]) == 0){
                    num1[0] ^= array[i];
                }else{
                    num2[0] ^= array[i];
                }
            }
        }
    }
    
    • 两个同样的数相异或后等于0
    • 两个一样的数a的和一个不一样b的数相异或后 (a ^ b ^ a)结果为b,并且与顺序无关
    • a ^ b ^ c ^ d ^ e ^ d ^ c ^ b ^ a = e
    • 利用这个条件,我们将所有的数都异或一遍,将得到要求的两个数相&的结果。(a ^ b ^ c ^ d ^ a ^ d = b ^ c)
    • 然后利用一个公式求出b和c之间的一个有差异的位,并按照这个位的值不同,将数组分为两组(aca,bdd) 然后分别再分别在两个组里全部相异或一次(a ^ c ^ a, b ^ d ^ d)
    • 这个表示差异的位的信息存在last里面,last是用来求一个二进制数的最后一个1的位置的算法(n = 10001100,(n - 1) & n= 10001000,last = 100)

    相关文章

      网友评论

        本文标题:剑指offer----数组中只出现一次的数

        本文链接:https://www.haomeiwen.com/subject/ptnxtftx.html