【leetcode刷题】T34-只出现一次的数字 II
【英文题目】（学习英语的同时，更能理解题意哟~）
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
【中文题目】
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
【思路】
本题和【T33-只出现一次的数字】类似，有两种解法：一是使用hash表，二是利用到数学。
hash表即为：使用字典存储元素及其个数，对所有元素进行计数，当元素个数为3时，弹出字典
数学方法即是按照异或的思想，把元素转换为二进制后，每一位上使得1+1+1=0，即对3求余（余数只可能为1和0）
【代码】
python版本
hash
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
d = {}
for n in nums:
d[n] = d.get(n, ) +
if d[n] == :
d.pop(n)
return d.keys()[]
二进制
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ls = [] *
for n in nums:
for i in range():
ls[ - i] += ((n >> i) & )
res =
for i in range():
res = res * + ls[i] %
# 负数
if ls[] % == :
res -= **
return res
C++版本
hash
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int, int> d;
for(int i=; i<nums.size(); i++){
if(d.find(nums[i]) == d.end())
d[nums[i]] = ;
else{
d[nums[i]]++;
if(d[nums[i]] == )
d.erase(nums[i]);
}
}
return d.begin()->first;
}
};
二进制
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = ;
int tmp;
for(int i=; i < ; i++){
tmp = ;
for(int j=; j < nums.size(); j++){
tmp += ((nums[j] >> i) & );
}
tmp = tmp % ;
res |= (tmp << i);
// cout << tmp << " " << res << endl;
}
return res;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
