【LeetCode】442. Find All Duplicates in an Array 解题报告（Python& C++）
2024-09-04 10:25:11
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/find-all-duplicates-in-an-array/description/
题目描述
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
题目大意
在一个数组中，有些数字出现了两次，有些数字出现一次。找出出现两次的所有数字。
解题方法
字典
使用字典统计出现次数。
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
map<int, int> count;
for (int num : nums) {
count[num] ++;
}
vector<int> res;
for (auto c : count) {
if (c.second == 2)
res.push_back(c.first);
}
return res;
}
};
原地变负
这个题的难点在于O(n)的时间复杂度和不用额外空间。下面的做法我是按照Discuss做的，使用了题目给的一个trick,1 ≤ a[i] ≤ n，这样使用a[i]-1把数组中该位置的元素求反，当再次遇到该位置时能够通过这个位置是负数来确定出现了两次。因为可能会对还没有扫描到的位置进行求反，所以当扫描到该位置的时候应该进行求绝对值操作。
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = []
for num in nums:
if nums[abs(num) - 1] < 0:
ans.append(abs(num))
nums[abs(num) - 1] *= - 1
return ans
C++代码如下：
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
const int N = nums.size();
vector<int> res;
for (int i = 0; i < N; i++) {
if (nums[abs(nums[i]) - 1] < 0)
res.push_back(abs(nums[i]));
nums[abs(nums[i]) - 1] *= -1;
}
return res;
}
};
日期
2018 年 2 月 6 日
2018 年 12 月 5 日 —— 周三啦！
最新文章
- Maven仓库搭建和配置
- 初识cache
- kernel 4.4.12 外部模块Makefile 脚本编写
- 相机标定简介与MatLab相机标定工具箱的使用（未涉及原理公式推导）
- UE4.11新特性：胶囊体阴影
- Handler Should be static or leaks Occur？
- NOIP2014感想
- selenium遍历控件集合
- 物联网操作系统HelloX开发人员入门指南
- 【转】gvim配置及相关插件安装
- 每天一个Linux命令（09）--touch命令
- Java_Date_02_截断日期到日
- 利用requirejs实现vue的模块化开发
- BOM 浏览器对象模型_当前窗口的浏览历史 history 对象
- 保密数据!泽宝曝光各个主要店铺收入 核心SKU数量少得惊人
- Git的安装和使用
- python函数进阶（函数参数、返回值、递归函数）
- vue-04-组件
- 【PyQt5-Qt Designer】QLineEdit 文本输入
- Getting Started withProcessing 第八章总结