leetcode算法: Find All Duplicates in an Array
2023-09-27 14:28:47 时间
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]
这道题描述的是:
给我们一个 长度为n 的列表,里面全都是整数 并且满足每个整数都是1到n之间的数
我们要做的是: 找到里面出现两次的整数
要求我们 使用O(n) 的时间复杂度和 O(1)的空间复杂度
描述一下思想:
这道题困扰了我很久,在网上查阅了一些代码,用了一些时间才搞懂。
O(n) 的时间复杂度 只允许一次遍历,就找到出现2次的元素
O(1) 的空间复杂度,我们不能开辟线性空间。
参考了网上大神的代码,他的想法是,把原本给我们的数组,当作hash来做散列映射。具体的做法是这样:
对一个数组 A = [X,X,X,X,X,X]
从头开始遍历,对每个元素 i :
如果 A[ 绝对值(i)-1 ] >0: 我们就让 A[ 绝对值(i)-1 ] = -A[ 绝对值(i)-1 ]
如果 A[ 绝对值(i)-1 ] <0: 绝对值(i)就是第二次出现,我们把它追加到结果列表
返回 结果列表
为什么这样就行呢:
1 列表长度是n,并且没个元素都是 1到n之间的数,所以 任何一个元素i ,用 绝对值(i) - 1 作下标,不会越界
2 初始情况下,数组每个元素都是正数(1到n之间) , 我们遍历数组:
每当第一次拿到一个数i,把 A[绝对值(i)-1] 该为负数,(i这个数值第一次出现,响应位置上的数字一定是正数,我们把他改成了负数)
如果我们拿到一个数i,这个数值是第二次出现,我们在取 A[绝对值(i)-1] 的时候,之前我们就把他改为负数了,所以, 绝对值(i) 这个数,这一次取到 一定是重复的。
把这个重复的数放到结果列表里
3 为什么 我们把里面的数字 取相反数,不做其他标记呢? 因为里面数字取相反数 我们还能用绝对值找到原来的数。这里每一个数在我们做映射算法的时候,会依据这个数找到一个数组的位置,所以不能用其他标记。
我的python代码:
1 class Solution(object):
2 def findDuplicates(self, nums):
3 """
4 :type nums: List[int]
5 :rtype: List[int]
6 """
7 res = []
8 for i in nums:
9 if nums[abs(i)-1] > 0:
10 nums[abs(i)-1] *= -1
11 else :
12 res.append(abs(i))
13 return res
14
15
16 if __name__ == '__main__':
17 s = Solution()
18 res = s.findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])
19 print(res)
相关文章
- 【LeetCode】最长回文子串 [M](Manacher算法)
- 【LeetCode】回文对 [H](Manacher算法)
- 【LeetCode】矩阵中的最长递增路径 [H](记忆化搜索)
- 2023-02-23 leetcode-查找算法-TwoSum-思考
- LeetCode 算法刷题目录 (Java)
- LeetCode_贪心算法_中等_846.一手顺子
- LeetCode_贪心算法_双端队列_中等_402.移掉 K 位数字
- LeetCode_贪心算法_中等_738.单调递增的数字
- LeetCode_滑动窗口_中等_395.至少有 K 个重复字符的最长子串
- LeetCode_递归_回溯算法_中等_22.括号生成
- LeetCode_单调栈_困难_85.最大矩形
- LeetCode_贪心算法_中等_55.跳跃游戏
- LeetCode_Boyer-Moore 投票算法_简单_169.多数元素
- LeetCode_回溯算法_简单_17.电话号码的字母组合
- LeetCode·每日一题·698.划分为 K 个相等的子集·递归回溯
- LeetCode·332.重新安排行程·DFS
- LRU算法&&LeetCode解题报告
- LeetCode::Sort List 具体分析
- LeetCode-876. 链表的中间结点(Goland实现)
- [LeetCode] 752. Open the Lock 开锁
- leetcode 算法 Excel表列序号 python实现
- leetcode算法:Trim a Binar Search Tree
- leetcode算法:Reshape the Matrix
- leetcode算法练习 JavaScript实现
- leetcode 239 滑动窗口最大值