【LeetCode】448. 找到所有数组中消失的数字
2023-09-14 09:13:23 时间
1.题目
要求:时间复杂度 O(n)
,空间复杂度 O(1)
。
2.思想
基于交换的思想。仔细阅读题目,其实可以发现本题的数据有个很好的条件:
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。
在这个条件下,我们就可以进一步的发现,其实这个数组可以更好的存放这些数字。比如对于输入: nums = [4,3,2,7,8,2,3,1]
,我们希望最后存储的数据格式是: nums = [1,2,3,4,2,3,7,8]
。即nums[i]=i+1
。但是因为有重复的数字,肯定不是所有的数都满足这个要求,那么再顺序遍历一下,就知道了缺失的数字了。
具体来说,步骤如下:
- (1)使用交换的方法,不停的将数字放到正确的位置
- (2)最后再遍历一次数组,找出缺失的数字即可
3.代码
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
cur = nums[i]
while( nums[cur-1] != cur) : # swap
nums[cur-1],nums[i] = nums[i],nums[cur-1]
cur = nums[i]
res = []
for i in range(len(nums)):
if nums[i] != i+1:
res.append(i+1)
return res
相关文章
- Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)
- Java实现 LeetCode 442 数组中重复的数据
- Java实现 LeetCode 303 区域和检索 - 数组不可变
- Java实现 LeetCode 138 复制带随机指针的链表
- Java实现 LeetCode 88 合并两个有序数组
- Java实现 LeetCode 79 单词搜索
- Java实现 LeetCode 4 寻找两个有序数组的中位数
- 【哈希表】LeetCode 560. 和为K的子数组【中等】
- LeetCode-667. 优美的排列 II【数组,数学】
- 279. 完全平方数——(LeetCode刷题)
- Python 刷Leetcode题库,顺带学英语单词(21)
- 【LeetCode 31】下一个排列
- LeetCode - 503 下一个更大元素 II
- Leetcode 1389. 按既定顺序创建目标数组
- Leetcode 1640. 能否连接形成数组(终于解决)
- Leetcode 1296. 划分数组为连续数字的集合(已解决)
- leetcode 217 Contains Duplicate 数组中是否有反复的数字
- LeetCode 263. 丑数
- LeetCode 61. 旋转链表