福永公司网站建设,观澜小学 网站建设,网页设计找工作,快速迁移网站题目 - 点击直达 1. 137. 只出现一次的数字 II 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 137. 只出现一次的数字 II 中等
1. 题目详情
1. 原题链接
LeetCode 137. 只出现一次的数字 II 中等
2. 题目要求
给你… 题目 - 点击直达 1. 137. 只出现一次的数字 II 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 137. 只出现一次的数字 II 中等
1. 题目详情
1. 原题链接
LeetCode 137. 只出现一次的数字 II 中等
2. 题目要求
给你一个整数数组 n u m s nums nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例 1 输入nums [2,2,3,2] 输出3 示例 2 输入nums [0,1,0,1,0,1,99] 输出99 提示 1 n u m s . l e n g t h 3 ∗ 104 1 nums.length 3 * 104 1nums.length3∗104 − 231 n u m s [ i ] 231 − 1 -231 nums[i] 231 - 1 −231nums[i]231−1 n u m s nums nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
3. 基础框架
● Cpp代码框架
class Solution {
public:int singleNumber(vectorint nums) {}
};2. 解题思路
1. 思路分析 ( 1 ) (1) (1) 哈希映射的思想把 n u m s nums nums数组中出现的数唯一映射到 u n o r d e r e d m a p i n t , i n t unordered_mapint, int unorderedmapint,int中第二个参数记录其出现的次数 ( 2 ) (2) (2) 遍历 n u m s nums nums数组并记录每个元素出现的次数 ( 3 ) (3) (3) 再次遍历 n u m s nums nums数组判断每个元素在 u n o r d e r e d m a p i n t , i n t unordered_mapint, int unorderedmapint,int中出现的次数
如果元素出现的次数是1则返回该元素反之则继续判断下一个元素直到 n u m s nums nums末尾为止。
2. 时间复杂度 O ( N ) O(N) O(N) 遍历了两遍数组 n u m s nums nums每次循环内进行的操作都是常数次总体是 2 ∗ N 2*N 2∗N 3. 代码实现
哈希映射
class Solution {
public:int singleNumber(vectorint nums) {// 哈希映射unordered_mapint, int m;for(auto e : nums){m[e];}for(auto e : nums){if(m[e] 1){return e;}}return -1;}
};暴力模拟
class Solution {
public:int singleNumber(vectorint nums) {sort(nums.begin(), nums.end());int one 0, two 1, three 2;while(one nums.size()){if(one nums.size() - 1 || nums[one] ! nums[two]){return nums[one];}one 3;two 3;three 3;}return -1;}
};通用模拟计数
class Solution {
public:int singleNumber(vectorint nums) {sort(nums.begin(), nums.end());int first 0;int second 0;int len 0;while(second nums.size()){if(nums[first] ! nums[second]){if(len 1){break;}len 0;first second;}second;len;}return nums[first];}
};T h e The The E n d End End
