【python-leetcode448-循环排序】找到所有数组中消失的数字
发布时间:2020-12-20 09:55:00 所属栏目:Python 来源:网络整理
导读:问题描述: 给定一个范围在? 1 ≤ a[i] ≤ n (?n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。 找到所有在 [1,n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假
问题描述: 给定一个范围在? 1 ≤ a[i] ≤ n (?n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。 找到所有在 [1,n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。 示例: 输入: 输出: ? 核心;循环排序法,让每个数字在其应该的位置上。注意数值和下标之间的关系 class Solution: def findDisappearedNumbers(self,nums: List[int]) -> List[int]: res=[] l=0 r=len(nums)-1 while l<=r: if nums[l] != nums[nums[l]-1]: nums[nums[l]-1],nums[l] = nums[l],nums[nums[l]-1] else: l+=1 for i in range(len(nums)): if i+1 != nums[i]: res.append(i+1) return res 比如:nums=[4,1] 过程: [7,4,1] [3,1] [2,1,8] [1,8] 最后再遍历一次数组:值!=下标+1,将下标+1加入到结果中。 结果: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |