当前位置:网站首页>哈希表应用:只出现一次的数字

哈希表应用:只出现一次的数字

2022-08-10 15:20:00 ^o^叶子^0^

目录

题目描述

AC代码

解析


题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

AC代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
	unordered_map<int,int>hashmap;
	for(auto & it:nums)++hashmap[it];
	for(auto & [key,value]:hashmap)if(value==1)return key;
	return 0;
    }
};

解析

很像python的字典。

unordered_map的内部实现了一个哈希表,有键和值对应,键不会重复,就像字典一样,页数与内容,用来解决这道题实在是太方便了,用切片提取vector的元素,把它作为哈希表的键,出现次数作为对应的值,哈希表还会自己新增进去,都不需要判断有没有,自己就会做判断,装完哈希表之后遍历一下找出出现次数为1的就可以了。

话说C++的切片,还能提取多个元素,我到目前为止,只知道在C++中,字符串、set、vector,以及今天学的unordered_map可以切片,不过,话说回来,哈希表是真的巨好用@[email protected]

原网站

版权声明
本文为[^o^叶子^0^]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_62264287/article/details/126259925