leetcode || 136、Single Number
來源：程序員人生 發布時間：2015-06-05 09:29:28 閱讀次數：3289次
problem：
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Hide Tags
Hash Table Bit
Manipulation
題意：1組數，只有1個數出現1次，其他數都出現兩次，找出這個數
thinking：
（1）考察位運算，C/C++的異或運算符為 ^
0^a=a;
a^a=0;
a^b=b^a;
(2)這道題的解法就出來了：n個數的異或結果就是待求數
code：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n=nums.size();
int ret=nums[0];
for(int i=1;i<n;i++)
ret^=nums[i];
return ret;
}
};
本題擴大，參考http://www.cnblogs.com/changchengxiao/p/3413294.html
1.1個數組中有兩個元素只出現1次，其他所有元素都出現兩次，求這兩個只出現1次的元素
[解題思路]
將數組所有元素都進行異或得到1個不為0的結果，根據這個結果中的不為0的某1位將數組分成兩組
將兩組中的元素進行異或，如兩個數組的異或值都不為0，則得到最后結果
2.1個數組中有1個元素只出現1次，其他所有元素都出現k次，求這個只出現1次的元素
[解題思路]
當k為偶數時，同lss
當k為奇數時，將數組中每一個元素的每位相加mod k，得到結果即位出現1次的元素，時間復雜度O(nlen)，空間復雜度為O(1)
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
