【牛客题霸题解】数组中只出现一次的数字(待更新java 、py)
数组中只出现一次的数字
http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
先考虑另一个问题,一个整型数组里除了一个数字之外,其他的数字都出现了两次,那把所有的数据异或起来,异或的结果就是那一个数字。(因为出现过两次的数字异或起来就抵消了)
对于这个题来说,如果把数字全异或起来,最后异或出来的结果是不同的那两个数的异或,然后随便从异或结果里面找一位1。我用的是lowbit方法,X&(-X)得到最低位的1,因为某一位上异或结果是1的话,说明要找两个数,这一位上一个是1,一个是0。那么就可以把原来数组中,这一位是1的分成一组,这一位是0的分成一组。这样就有了两组每一组中会包含一个不同的数和一部分出现两次的数。 然后组内异或就可以了。
#include<iostream> #include<vector> using namespace std; class Solution{ public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2){ int XOR = 0; int len = data.size(); for(int i = 0 ;i < len ; i++) { XOR ^=data[i]; } int lowbit = XOR&(-XOR); *num1 = 0; *num2 = 0; for(int i = 0 ;i < len ; i++) { if(data[i]&lowbit){ *num1 ^=data[i]; } else{ *num2 ^=data[i]; } } } }; int main() { Solution S; int N; int num1,num2; cin >> N; vector<int> data(N); for(int i = 0 ;i < N; i++) { cin >> data[i]; } S.FindNumsAppearOnce(data,&num1,&num2); cout<<num1<<" "<<num2; return 0; } /* 6 1 1 3 3 7 8 */
牛客题霸题解 文章被收录于专栏
QAQ