LeetCode136:Single Number

题目:

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?

解题思路:

很简单的一题,直接用异或运算解决:连个相同数进行异或结果为0,0与任何数异或结果为原数

也可先进行排序再遍历排序后的数组,当某个数没有重复时,结果就是它了

也可用bitmap进行,不多说了。

实现代码:

#include <iostream>

using namespace std;
/*
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?
*/
class Solution {
public:
int singleNumber(int A[], int n) {
int ret = ;
for(int i = ; i < n; i++)
ret ^= A[i];
return ret; }
}; int main(void)
{
int arr[] = {,,,,,,};
int len = sizeof(arr) / sizeof(arr[]);
Solution solution;
int once = solution.singleNumber(arr, len);
cout<<once<<endl;
return ;
}
上一篇:scrapy分布式的几个重点问题


下一篇:python基础之map/reduce/filter/sorted