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

牛客网-剑指office-数组中只出现一次的数字

程序员文章站 2022-03-01 13:33:02
...

题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解法一:
思路:首先我们会想到一个数组中只有一个数字出现一次的那道题。我们可以用异或的思想。
但这道题中有两个数字都只出现了一次,我们仍然可以利用异或的思想。我们先需要将原始数组分为两个数组,并且需要同时满足:1、两个只出现一次的数字出现在不同的数组中。2、两个相同的数字不能被分在不同的数组中。
我们可以首先遍历一遍数组,将每个数字异或。由于有两个不同的数字,所以得到的结果tmp一定不等于0.我们可以找出该结果tmp的二进制数的第一位等于1的位置index,利用这一位可以区分这两个不同的数字,并且可以保证相同的数字被分在了相同的数组中。代码如下所示:

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int tmp=0;
        for(int i=0;i<data.size();++i)
            tmp=tmp^data[i];
        unsigned int index =findfirst1(tmp);
        *num1 = 0;
        *num2 = 0;
        for(int i=0;i<data.size();++i)
        {
            if(isbit1(data[i],index))
                num1[0]=num1[0]^data[i];
            else
                num2[0]=num2[0]^data[i];
        }
        }
    unsigned int findfirst1(int num)
    {
        int index = 0;
        while(((num&1)==0)&&(index<32))
        {
            num=num>>1;
            ++index;
        }
        return index;
    }
    int isbit1(int num,unsigned int index)
    {
        num=num>>index;
        return num&1==1;
    }
};

解法二:
思路:建立一个set容器,然后遍历数组,如果数字已经存在于set容器中,则删除该数字,如果没有存在,则将该数字放入set容器中,最后剩下的数就是只出现一次的两个数字。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        set<int> tmp;
        for(int i=0;i<data.size();++i)
        {
            if(tmp.count(data[i])==1)
                tmp.erase(data[i]);
            else
                tmp.insert(data[i]);
        }
        vector<int> ans;
        for(set<int>::iterator iter = tmp.begin();iter!=tmp.end();++iter)
        {
            ans.push_back(*iter);
        }
        *num1 = ans[0];
        *num2 = ans[1];
    }
};

python的解法:
思路:利用c++的第二种解法的思路。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        ans = []
        for num in array:
            if num in ans:
                ans.remove(num)
            else:
                ans.append(num)
        return ans