We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
这是一道简单题,但是题目中的附加条件使得这道题别具趣味性。
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
1 ≤ a[i] ≤ n
n
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
[1, n]
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入: [4,3,2,7,8,2,3,1] 输出: [5,6]
来源:力扣(LeetCode)
从题意出发,数组中重复元素会挤占消失元素的位置,我们举个比较简单的例子:
[1, 2, 3, 4, 5, 1, 7]
可以看到元素 1 挤占了元素 6 的空间,我们可以很轻松地通过判断 nums[i] == i 来找到答案。
1
6
nums[i] == i
这意味着,如果我们能对输入数组进行某种变换,使得数组中的元素满足某种特定地排列方式,那么我们只需要找出不等于索引值的元素所在的索引,就找到了消失的数字。
举个稍微复杂点的例子,比如示例输入:
[4, 3, 2, 7, 8, 2, 3, 1]
为了方便理解,我们对其排个序:
[1, 2, 2, 3, 3, 4, 7, 8]
手动变换为我们想要的数组形式:
[1, 2, 3, 4, 2, 3, 7, 8]
可以看到,索引 5 和 6 处(为方便表述,本文索引是从 1 开始)的元素满足了 nums[i] != i,所以 [5, 6] 就是我们要的答案。
5
nums[i] != i
[5, 6]
那么该如何进行这种变换呢?可以看到题中特地指出 n == len(nums),这提示我们可以用元素值和索引值之间的映射关系来解决问题,过程如下所示,其中 ^ 表示当前索引:
n == len(nums)
^
# 原始数组 [4, 3, 2, 7, 8, 2, 3, 1] ^
先判断当前索引指向的数字是否满足 nums[i] == i 以及 nums[nums[i]] == nums[i]:
nums[nums[i]] == nums[i]
swap(nums[i], nums[nums[i]])
逐次进行,我们得到以下步骤:
[7, 3, 2, 4, 8, 2, 3, 1] ^ [3, 3, 2, 4, 8, 2, 7, 1] ^ [2, 3, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 8, 2, 7, 1] ^ [3, 2, 3, 4, 1, 2, 7, 8] ^ [1, 2, 3, 4, 3, 2, 7, 8] ^ [1, 2, 3, 4, 3, 2, 7, 8] ^ [1, 2, 3, 4, 3, 2, 7, 8] ^ [1, 2, 3, 4, 3, 2, 7, 8] ^ [1, 2, 3, 4, 3, 2, 7, 8]
可以看到,数组逐渐变得有序,而且这种变换只需要 $O(N)$ 的时间复杂度,并且无需额外空间。
class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: nums, i = [x - 1 for x in nums], 0 # 预处理 while i < len(nums): if nums[i] == i and nums[nums[i]] == nums[i] tmp, nums[i] = nums[i], nums[nums[i]] nums[tmp] = tmp # 执行交换 else: i += 1 ret = [] # 找出消失的数字 for i in range(len(nums)): if i != nums[i]: ret.append(i + 1) return ret
The text was updated successfully, but these errors were encountered:
相关题目:287. 寻找重复数。
Sorry, something went wrong.
No branches or pull requests
题目
给定一个范围在
1 ≤ a[i] ≤ n
(n
= 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。找到所有在
[1, n]
范围之间没有出现在数组中的数字。您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
来源:力扣(LeetCode)
解读
从题意出发,数组中重复元素会挤占消失元素的位置,我们举个比较简单的例子:
可以看到元素
1
挤占了元素6
的空间,我们可以很轻松地通过判断nums[i] == i
来找到答案。这意味着,如果我们能对输入数组进行某种变换,使得数组中的元素满足某种特定地排列方式,那么我们只需要找出不等于索引值的元素所在的索引,就找到了消失的数字。
举个稍微复杂点的例子,比如示例输入:
为了方便理解,我们对其排个序:
手动变换为我们想要的数组形式:
可以看到,索引
5
和6
处(为方便表述,本文索引是从1
开始)的元素满足了nums[i] != i
,所以[5, 6]
就是我们要的答案。那么该如何进行这种变换呢?可以看到题中特地指出
n == len(nums)
,这提示我们可以用元素值和索引值之间的映射关系来解决问题,过程如下所示,其中^
表示当前索引:先判断当前索引指向的数字是否满足
nums[i] == i
以及nums[nums[i]] == nums[i]
:swap(nums[i], nums[nums[i]])
。逐次进行,我们得到以下步骤:
可以看到,数组逐渐变得有序,而且这种变换只需要$O(N)$ 的时间复杂度,并且无需额外空间。
代码
The text was updated successfully, but these errors were encountered: