当前位置：首页 > news >正文

LeetCode 137. 只出现一次的数字 II 中等

news 来源：原创 2024/5/12 5:58:51

题目 - 点击直达

1. 137. 只出现一次的数字 II 中等
- 1. 题目详情
- - 1. 原题链接
  - 2. 题目要求
  - 3. 基础框架
- 2. 解题思路
- - 1. 思路分析
  - 2. 时间复杂度
  - 3. 代码实现

1. 137. 只出现一次的数字 II 中等

1. 题目详情

1. 原题链接

LeetCode 137. 只出现一次的数字 II 中等

2. 题目要求

给你一个整数数组 $n u m s$ ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 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$
$- 231 <= n u m s [i] <= 231 - 1$
$n u m s$ 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

3. 基础框架

● Cpp代码框架

class Solution {
public:int singleNumber(vector<int>& nums) {}
};

2. 解题思路

1. 思路分析

$(1)$ 哈希映射的思想，把 $n u m s$ 数组中出现的数唯一映射到 $unordered_map<int, int>$ 中，第二个参数记录其出现的次数；
$(2)$ 遍历 $n u m s$ 数组，并记录每个元素出现的次数；
$(3)$ 再次遍历 $n u m s$ 数组，判断每个元素在 $unordered_map<int, int>$ 中出现的次数：

如果元素出现的次数是1，则返回该元素；
反之则继续判断下一个元素，直到 $n u m s$ 末尾为止。

2. 时间复杂度

$O (N)$

遍历了两遍数组 $n u m s$ ，每次循环内进行的操作都是常数次，总体是 $2 * N$

3. 代码实现

哈希映射

class Solution {
public:int singleNumber(vector<int>& nums) {// 哈希映射unordered_map<int, 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(vector<int>& 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(vector<int>& 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];}
};