题目链接:https://leetcode.cn/problems/single-number/
这个题做出来了,两种方法:1)借助hash表,key是数组中的数字,value是出现次数,第一次遍历数组,把数字和出现次数存到hash表,第二次遍历hash表,把出现次数=1的数字返回;2)先把数组排序,遍历比较排序后的连续2个数字,并记录相等的数字的次数,如果连续次数不超过1,表示数字没有重复,返回即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Solution { public: /* int singleNumber(vector<int>& nums) { unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { if (map.count(nums[i])) { map[nums[i]]++; } else { map[nums[i]] = 1; } } auto iter = map.begin(); while (iter != map.end()) { if (iter->second == 1) { return iter->first; } iter++; } return nums[0]; } */ int singleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); auto iter = nums.begin(); int count = 1; for (; iter != nums.end(); iter++) { if (iter+1 == nums.end()) { return *iter; } if (*iter == *(iter+1)) { count++; } else { if (count == 1) { return *iter; } else if (count > 1) { count = 1; } } } return nums[0]; } }; |