LintCode: Single Number

  1. 云栖社区>
  2. 博客>
  3. 正文

LintCode: Single Number

技术小哥哥 2017-11-13 21:52:00 浏览491
展开阅读全文

(1)异或操作

3^3=0

(2)for (auto &i : Obejuct) {}

复制代码
 1 class Solution {
 2 public:
 3     /**
 4      * @param A: Array of integers.
 5      * return: The single number.
 6      */
 7     int singleNumber(vector<int> &A) {
 8         // write your code here
 9         int ret = 0;
10         for (auto &i : A) {
11             ret ^= i;
12         }
13         return ret;
14     }
15 };
复制代码

 

本题扩展

1.一个数组中有两个元素只出现一次,其他所有元素都出现两次,求这两个只出现一次的元素

[解题思路]

将数组所有元素都进行异或得到一个不为0的结果,根据这个结果中的不为0的某一位将数组分成两组

将两组中的元素进行异或,如两个数组的异或值都不为0,则得到最后结果

 

2.一个数组中有一个元素只出现1次,其他所有元素都出现k次,求这个只出现1次的元素

[解题思路]

当k为偶数时,同lss

当k为奇数时,将数组中每个元素的每一位相加mod k,得到结果即位出现1次的元素,时间复杂度O(nlen),空间复杂度为O(1)


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/p/5109556.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
技术小哥哥
+ 关注