136. 只出现一次的数字
题目:
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例:
示例 1 :
输入:nums = [2,2,1]
输出:1
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
示例 3 :
输入:nums = [1]
输出:1
提示:
解题:
方法一:集合法
使用集合unordered_set
存储数字。遍历数组中的每个数字,如果集合中没有该数字,则将该数字加入集合,如果集合中已经有该数字,则将该数字从集合中删除,最后剩下的数字就是只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> numSet;
for(int num : nums) {
// 如果集合中已经有当前数字,则从集合中删除
if(numSet.find(num) != numSet.end()) {
numSet.erase(num);
} else {
// 如果集合中没有当前数字,则加入集合
numSet.insert(num);
}
}
// 集合中剩下的就是只出现一次的数字
return *numSet.begin();
}
};
方法二:哈希表法
使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数,并更新哈希表,最后遍历哈希表,得到只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> numCount;
// 遍历数组,更新哈希表中数字的出现次数
for(int num : nums) {
numCount[num]++;
}
// 遍历哈希表,找到只出现一次的数字
for(auto& pair : numCount) {
if(pair.second == 1) {
return pair.first;
}
}
// 如果没有找到只出现一次的数字,返回默认值0
return 0;
}
};
方法三:元素之和两倍性质
由于集合保证元素无重复,所以使用集合unordered_set
不重复的存储数组的元素,也就是每个元素只存储一次,重复的不存储,计算它们的和,就相当于所有数字的两倍之和。然后将原数组中的元素全部相加,就相当于只出现了一次的元素加上全部出现了两次的元素。如此看来,它们的差就是就差了一个只出现一次的元素了。
class Solution {
public:
int singleNUmber(vector<int>& nums) {
unordered_set<int> numSet;
int sumSet = 0;
int sumArray = 0;
// 遍历数组,更新集合中的元素之和和数组中的元素之和
for(int num : nums) {
if(numSet.find(num) == numSet.end()) {
numSet.insert(num);
sumSet += num;
}
sumArray += num;
}
// 计算集合中的元素之和的两倍减去数组中的元素之和,得到只出现一次的数字
return 2*sumSet - sumArray;
}
};
上述三种解法都需要额外使用 O(n) 的空间,其中 n 是数组长度。
方法四:位运算(线性时间复杂度,常数空间复杂度)
异或运算有以下三个性质:
假设数组中有 2m+1 个数,其中有 m 个数各出现两次,一个数出现一次。
令 a1 、a2 、…、am为出现两次的 m 个数,am+1为出现一次的数。
根据性质 3,数组中的全部元素的异或运算结果总是可以写成如下形式:
- (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1
- 0⊕0⊕⋯⊕0⊕am+1=am+1
因此,数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(auto e : nums) ret ^= e;
return ret;
}
};
- 时间复杂度:O(n),其中 n 是数组长度。只需要对数组遍历一次。
nt>& nums) {
int ret = 0;
for(auto e : nums) ret ^= e;
return ret;
}
};
**复杂度分析**
- 时间复杂度:O(n),其中 n 是数组长度。只需要对数组遍历一次。
- 空间复杂度:O(1)。
原文地址:https://blog.csdn.net/m0_53485135/article/details/134593936
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_22550.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!