136. Single Numbe
难度:Easy
刷题内容
原题连接
- https://leetcode.com/problems/single-number/
内容描述
Given a non-empty 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?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
思路1 **- 时间复杂度: O(n)*- 空间复杂度: O(1)***
用异或运算解决这道题，这里用了异或运算的几个性质，异或的交换和结合律，还有两个相同的数异或的值为0，任何数异或0为它本身。有了这些基本只是之后，我们只要对数组进行异或运算得到的数就是答案。因为只有一个数是 single number，其余的数都成双，那么最后就相当于single number异或0
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = nums[0];
for(int i = 1;i < nums.size();++i)
ans ^= nums[i];
return ans;
}
};
思路2 **- 时间复杂度: O(n)*- 空间复杂度: O(1)***
第二种思路将所有数转成二进制，记录下每一位不为2的倍数，这些位为1，其余为0，求出最后的数就是答案。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int arr[32][2],t = 1;
memset(arr,0,sizeof(arr));
for(int i = 0;i < nums.size();++i)
{
int count1 = 0;
if(nums[i] < 0)
{
t *= -1;
nums[i] *= -1;
}
while(nums[i])
{
arr[count1++][nums[i] % 2]++;
nums[i] /= 2;
}
}
int ans = 0;
for(int i = 0;i < 32;++i)
if(arr[i][1] % 2)
ans += pow(2,i);
if(t < 0)
ans *= -1;
return ans;
}
};
