LeetCode-136. 只出现一次的数字【哈希表,位运算,排序,暴力】
2023-09-14 09:01:27 时间
LeetCode-136. 只出现一次的数字【哈希表,位运算,排序,暴力】
题目描述:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
该题力扣
解题思路一:哈希表
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> mp;
int n=nums.size();
for(int i=0;i<n;++i) ++mp[nums[i]];
for(auto num:mp) if(num.second==1) return num.first;
return 0;
}
};
时间复杂度:O(n)
空间复杂度:O(n)
解题思路二:排序
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size(),temp=nums[0],count=0;
for(int i=0;i<n;++i){
if(temp==nums[i]) ++count;
else if(count==1) return temp;
else{
count=1;
temp=nums[i];
}
}
return temp;
}
};
时间复杂度:O(nlogn)
空间复杂度:O(1)
解题思路三:位运算,这个一定要看,非常巧妙!!!
异或操作的性质:
1.任何数和 0 做异或运算,结果仍然是原来的数,即 a⊕0=a。
2.任何数和其自身做异或运算,结果是 0,即 a⊕a=0。出现两次的数异或结果是0
3.异或运算满足交换律和结合律,即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
由此可知,将数组中所有数进行一次异或操作,所有出现两次的数全部变为0,最终剩下仅仅出现一次的数!
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(auto num:nums) ans^=num;
return ans;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
解题思路四:暴力
两个for循环,代码略
时间复杂度:O(n2)
空间复杂度:O(1)
相关文章
- [LeetCode] Binary Tree Paths - 二叉树基础系列题目
- Java实现 LeetCode 792 自定义字符串排序(暴力)
- Java实现 LeetCode 792 自定义字符串排序(暴力)
- Java实现 LeetCode 791 自定义字符串排序(桶排序)
- Java实现 LeetCode 768 最多能完成排序的块 II(左右便利)
- Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
- Java实现 LeetCode 738 单调递增的数字(暴力)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 689 三个无重叠子数组的最大和(换方向筛选)
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 430 扁平化多级双向链表
- Java实现 LeetCode 1013 将数组分成和相等的三个部分
- Java实现 LeetCode 342 4的幂
- Java实现 LeetCode 324 摆动排序 II
- Java实现 LeetCode 66 加一
- (LeetCode 21)Merge Two Sorted Lists
- 【刷题】【LeetCode】000-十大经典排序算法
- 每日一道 LeetCode (18):删除排序链表中的重复元素
- 【二分】LeetCode 33. 搜索旋转排序数组【中等】
- LeetCode(43):字符串相乘
- LeetCode(33):搜索旋转排序数组
- LeetCode-2363. 合并相似的物品【哈希表,排序】
- LeetCode-1636. 按照频率将数组升序排序【数组,哈希表,排序】
- LeetCode-937. 重新排列日志文件【stable_sort(),自定义排序】
- (链表专题) 725. 分隔链表 ——【Leetcode每日一题】
- leetCode 31.Next Permutation (下一个字典序排序) 解题思路和方法
- LeetCode 768. 最多能完成排序的块 II
- 【LeetCode】498. 对角线遍历
- 【LeetCode】148. 排序链表