【剑指Offer】（数组）数组中只出现一次的数字（位运算）

秒速五厘米 2022-03-16 12:50 137阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_e02fdb54d7524710a7d664d082bb7811_tpId_13_tqId_11193_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

class Solution { 
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { 
            if (data.size()<2) return;
            //方法1：先排序，后判断，复杂度O(nlogn)
            /*sort(data.begin(),data.end()); vector<int> res; if (data[0]!=data[1]) res.push_back(data[0]); if (data[data.size()-1]!=data[data.size()-2]) res.push_back(data[data.size()-1]); for(int i=1;i<data.size()-1;i++){ if (data.size()==2) break; if(data[i]!=data[i-1] && data[i]!=data[i+1]){ res.push_back(data[i]); } } *num1=res[0]; *num2=res[1];*/
            
            //方法2：用异或操作
            //[1]依次异或数组的每个元素，并找到结果中第一个为1的位的位置index
            int ans=data[0];
            for (int i=1;i<data.size();i++)
                ans^=data[i];
            int index=FindFirst1(ans);
            //[2]以第index位是不是1为标准把原数组划分成两个子数组，每个子数组分别异或，得到的结果即为只出现一次的数字
            for (int i=0;i<data.size();i++){ 
                if(IsIndex1(data[i],index))
                    (*num1)^=data[i];
                else
                    (*num2)^=data[i];
            }
    
        }
        int FindFirst1(int num){ 
            //找到数字中第一个为1的位的位置
            int index=0;
            while((num&1)==0){ 
                num=num>>1;//右移一位
                index++;
            }
            return index;
        }
        bool IsIndex1(int num,int index){ 
            //判断数字num中的第index位是否为1
            num=num>>index;
            return (num&1);
        }
    };

[https_www.nowcoder.com_practice_e02fdb54d7524710a7d664d082bb7811_tpId_13_tqId_11193_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking