欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指offer】数组中只出现一次的两个数字(数组)

程序员文章站 2022-03-08 16:23:40
...

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

1.hash

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        //遍历一遍数组,用map记录出现的次数,然后再遍历一遍数组,找出出现1次的数字。
        unordered_map<int, int> hash;
        for (auto x : data) hash[x] ++;
        vector<int> num;
        for (auto x : data) {
            if (hash[x] == 1) {
                num.push_back(x);
            } 
        }
        *num1 = num[0];
        *num2 = num[1];
    }
};

2.异或

题解

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
    //异或^
    // x ^ x = 0
    // x ^ 0 = x
    // x ^ y = z
    int sum = 0;//num1^ num2
    for(auto x : data) sum ^= x;
    //怎么拆分
    //二进制表示中一定有一位存在不同 1 0
    int k = 0;
    *num1 = 0;
    while(!(sum >> k & 1)) k ++;//通过第k位是否为1分组
    for(auto x : data)
        if(x >> k & 1)
        *num1 ^= x;//num1
        
    *num2 = sum ^ *num1;// num1^num2^num1 = num2
    }
};

3.自己写的low代码

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
    {
        int n=data.size();
        vector<int> num;
        for(int i=0;i<n;i++){
            int count=0;
            for(int j=0;j<n;j++){
                if(data[i]==data[j]) count++;
            }
            if (count==1) {
                num.push_back(data[i]);
            }
        }
        *num1=num[0];
        *num2=num[1];
    }
};