首页 > 代码库 > 【算法编程】找出仅仅出现一次的数-singleNumber
【算法编程】找出仅仅出现一次的数-singleNumber
题目意思:
一个数值数组中,大部分的数值出现两次,仅仅有一个数值仅仅出现过一次,求编程求出该数字。
要求,时间复杂度为线性,空间复杂度为O(1).
解题思路:
1.先排序。后查找。
因为排序的最快时间是O(nlogn), 所以这样的方法不能满足时间的要求。
2.其他技巧来解决:
依据主要的计算机组成原理的知识。採用”异或运算“来巧妙的完毕。
异或运算非常easy:
0^0=0
1^1=0
1^0=0^1=1
也就是说同样则为0,不同则为1.
所以不论什么同样的两个数的异或运算值结果为0。
0与不论什么数进行异或运算等于该值。
所以,我们仅仅须要将全部的数字进行异或运算一次(O(N)),它的结果就是我们要找的。仅仅出现过一次的值。
#include <iostream>
#include<vector>
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(vector<int>& nums)
{
vector<int>::iterator it;
it=nums.begin();
int sum=*it;
for (it=nums.begin()+1;it<nums.end();it++)
{
sum=sum^(*it);
}
return sum;
}
};
int main()
{
Solution instance = Solution();
vector<int> nums;
std::vector<int>::iterator it;
it = nums.begin();
int t;
while(cin>>t)
{
it =nums.insert (it,t);
}
cout << instance.singleNumber(nums) << endl;
return 0;
}
【算法编程】找出仅仅出现一次的数-singleNumber
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。