剑指offer 数组中只出现一次的数字 傷城~ 2022-06-15 01:12 113阅读 0赞 # 1.题目描述 # 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 # 2.分析 # 之前做过找出数组中唯一一个只出现一次的数组,[leetcode 136. Single Number][],通过异或的方法求解。 本题需找出两个只出现一次的数字,所以需要想办法将数组分为2个子数组,两个数字分别在一个子数组,然后再采用异或的方式。 步骤: 1)数组的所有元素异或,得到的结果必定非0,假设为n 2)找出n对应二进制最右边位的1所在bit 3)依据该bit位是否为1,将数组的元素分成两个子数组。出现相同的数字必然在同一数组,而两个只出现依次的数字必然在不同的数组 4)子数组的元素做异或,得到只出现一次的数字。 # 3.代码 # class Solution { public: void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) { int result = 0; for (int n : data) result ^= n; int bit = 1; while (!(result&bit)) { bit = bit << 1; } *num1 = 0; *num2 = 0; for (int n : data) { if (n&bit) *num1 ^= n; else *num2 ^= n; } cout<<num1<<" "<<num2<<endl; } }; [leetcode 136. Single Number]: http://blog.csdn.net/my_lovely_lemon_tree/article/details/71066057
还没有评论,来说两句吧...