【LeetCode】马三来刷题之 Single Number

最近每天刷题又找回了大一大二时天天晚上在机房刷ACM的那种感脚~，题目链接：https://leetcode.com/problems/single-number/   

136. Single Number

 

• Total Accepted: 155864
• Total Submissions: 301077
• Difficulty: Easy

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?

Subscribe to see which companies asked this question

同样是两种方法过的，第一种方法是使用STL的map进行统计，如果一个数字出现出现一次，则将其对应的键的值进行++操作，最后遍历整个map,

一旦发现值为1的就return 该键值对的键。第二种方法是先对数组排序，然后前一个和后一个依次相互比较，一旦发现有不同的，就返回前者，

如果遍历到num.size()-2为止还没有发现有不同的，那唯一的一个不同的值肯定就是最后一个了，所以直接return nums[nums.size()-1]。

第一种方法：

int singleNumber(vector<int>& nums) {if(nums.empty())return 0;map<int,int> m;for(int i=0;i<nums.size();i++){m[nums[i]]++;}for(map<int,int>::iterator it=m.begin();it!=m.end();it++){if((*it).second==1){return (*it).first;}}return 0; }

第二种方法;

int singleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());for(int i=0;i<nums.size()-2;){if(nums[i]!=nums[i+1])return nums[i];i+=2;}return nums[nums.size()-1]; }

每天一道题，保持新鲜感，就这样~

总结

以上是生活随笔为你收集整理的【LeetCode】马三来刷题之 Single Number的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。