[LeetCode]Single Number, Single Number II & Single Number III

2018-01-16 12:40:01来源:网络收集作者:咖啡不加糖人点击

分享

阿里云爆款
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?


题目大意:



  给你一个int型数组,在这个数组中只有一个元素只出现过一次,其他元素都恰好出现两次。找出只出现了一次的这个元素。但是这里要求时间复杂度为O(n),空间复杂度要求为O(1)。



分析:

  从二进制的角度来看这个问题,这是一个计数问题。我们首先考虑一个比特的情况:如果给你两个1和一个0这个时候答案应该是0,因为1出现了两次,而0只出现了一次。看到这里,我们会发现,出现次数就相当于对某一个比特位进行计数,而计数的次数与重复的次数有关系。此时我们只需要设计一个计数器来对这一位进行计数,只是这个计数器是每记到二就自动清零。那么这个计数器就是一个模二的加法器,巧合的是模二加法器就是异或运算。


  由于每一个比特都是独立的,所以对于一个int数的32个比特而言每一个比特都可以这么做。而多余的那个int的每一个比特由于这个数只出现一次,因此计算到最后最后剩下的那些比特位为1的恰好组成了这个数。于是我们的算法就是遍历数组对每一个元素进行异或运算(按位的模二加法运算)。

C++代码:class Solution {
public:
int singleNumber(vector& nums) {
int ret=0;
for(int num :nums)
ret=ret^num;
return ret;
}
};
Single Number II
问题描述:

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台