程序员人生 网站导航

leetcode || 136、Single Number

栏目:框架设计时间:2015-06-05 09:29:28

problem:

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?

Hide Tags
 Hash Table Bit Manipulation
题意:1组数,只有1个数出现1次,其他数都出现两次,找出这个数

thinking:

(1)考察位运算,C/C++的异或运算符为  ^

0^a=a;

a^a=0;

        a^b=b^a;

(2)这道题的解法就出来了:n个数的异或结果就是待求数

code:

class Solution { public: int singleNumber(vector<int>& nums) { int n=nums.size(); int ret=nums[0]; for(int i=1;i<n;i++) ret^=nums[i]; return ret; } };


本题扩大,参考http://www.cnblogs.com/changchengxiao/p/3413294.html


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

[解题思路]

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

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



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

[解题思路]


当k为偶数时,同lss


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

最新技术推荐