频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
[Leetcode]Single Number
2019-11-13 14:57:53         来源:CR_Peace的专栏  
收藏   我要投稿

Given an array of integers, every element appears twice except for one. Find that single one.

最近两个月事情很多,论文开题,家庭变故,都没有时间学习、做题,也没有时间写博客。现在回来再看感觉自己之前很多东西都做的不到位,所以把之前做过的题目也都翻出来做一下,温故知新嘛~

现在回忆一下,这是我做的第一道leetcode题目,也是我最初接触算法的时候做的。当时拿到题目简直是丈二和尚,感觉被leetcode的高深莫测深深折服了:罄聪肓撕芫酶芯跤帽究贫昙堆Ч氖萁峁估锏墓1砜梢越饩稣飧鑫侍,但是苦于c++水平太低,对关联容器这种外星物种更是一无所知,所以就一直没能实现。然后就开始猥琐的上网搜答案,答案一边倒倒向用位运算——异或解决这个问题,又一次感觉自己的智商被碾压。

任何数和它本身异或都得零,看到这句话瞬间感觉好猥琐(可以脑补屌丝码农自我安慰的场景,事后四大皆空,更不可能有孩子)。任何数和零异或都得它本身,这......屌丝终归是屌丝TT

言归正传,下边是这个思路的代码

 

class Solution{
public:
	int singleNumber(int A[], int n) {
		int answer = A[0];
		for(int i = 1;i < n; i++){
			answer = answer ^ A[i];
		}
		return answer;
	}
};

再说哈希表的思路,后来用了关联容器map来实现,自己测试过了,但是OJ系统报存储空间溢出。这次温习又用同样的方法尝试了下竟然过了,虽然这个方法空间复杂度是O(n),但总觉得这个方法比较实在,或者说比较通用,改变数组元素的重复次数依然使用(而位运算不行)用它也可以解决Single Number II。下面是代码:

 

 

class Solution{
public:
	int singleNumber(int A[], int n) {
		map m;
		for (int i = 0; i < n; i++){
			if (m.count(A[i])){
				m[A[i]]++;
			}
			else{
				m[A[i]] = 1;
			}
		}
		for (map::iterator it = m.begin(); it != m.end(); it++){
			if (it->second == 1) return it->first;
		}
		return 0;
	}
};

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:1027. Colors in Mars
下一篇:BZOJ 2326 HNOI 2011 数学作业 矩阵乘法
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 全峰安全联盟--致力于做实用的IT技术学习网站