剑指Offer-40.数组中只出现一次的数字(C++/Java)

题目：

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

分析：

我们知道，两个相同的数字异或的结果等于0，所以利用这个性质将数组中所有的数字异或，求得的结果，就是两个只出现一次数字异或的结果。而且这两个数字异或的结果肯定不为0，或者说结果数字二进制表示一定有一位为1，我们以第一个为1的位置作为区分数组中数字的条件，这样便能将两个数字分到两个数组中，再分别异或每一个数组中的数字，最后的结果便是这两个只出现了一次的数字。

程序：

C++

class Solution {

public:

    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        if(data.size() == )

            return;

        int flag = data[];

        for(int i = ; i < data.size(); ++i){

            flag ^= data[i];

        }

        int d = ;

        while((flag & d) == ){

            d = d << ;

        }

        *num1 = *num2 = ;

        for(int i = ; i < data.size(); ++i){

            if((data[i] & d) != ){

                *num1 ^= data[i];

            }

            else{

                *num2 ^= data[i];

            }

        }

    }

};

Java

//num1,num2分别为长度为1的数组。传出参数

//将num1[0],num2[0]设置为返回结果

public class Solution {

    public void FindNumsAppearOnce(int [] array, int num1[] ,int num2[]) {

        if(array == null || array.length == 0)

            return;

        int flag = 0;

        for(int i : array)

            flag ^= i;

        int d = 1;

        while((flag & d) == 0) {

            d = d << 1;

        }

        for(int i : array) {

            if((i & d) == 0) {

                num1[0] ^= i;

            }

            else {

                num2[0] ^= i;

            }

        }

    }

}

巴特西

剑指Offer-40.数组中只出现一次的数字(C++/Java)

题目：

分析：

程序：

最新文章

热门文章