打卡力扣题目十三

目录

 一、问题

二、解题方法一

 三、解题方法二

四、方法的区别 

 关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
 

 一、问题
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]
 

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n

二、解题方法一
def findDisappearedNumbers(nums):
    n = len(nums)
    for num in nums:
        x = (num - 1) % n
        nums[x] += n
    result = []
    for i in range(n):
        if nums[i] <= n:
            result.append(i + 1)
    return result
这段代码实现了一个函数 `findDisappearedNumbers`,用于找出给定数组中所有在区间 [1, n]
范围内但没有出现在原数组中的数字。该函数的实现过程如下：

  1. 首先，我们获取输入数组 `nums` 的长度 `n`,并定义一个变量 `x`。对于每个数字 `num`,我们将其减去 1 并对数组长度取模，得到的结果即为它在原数组中应该出现的位置。然后，我们将该位置的元素加上数组长度，这样就可以将原本在该位置出现的数字变为不在数组中的状态。具体来说，假设原数组中第 i 个位置的元素为 a[i],则经过上述操作后，a[i] - n 就会变成一个负数，表示该数字已经不在原数组中了。

  2. 接着，我们遍历整个数组 `nums`,找到所有仍然小于等于数组长度的下标，这些下标对应的数字就是没有出现在原数组中的数字。具体来说，我们使用一个循环来遍历数组 `nums`,对于每个下标 `i`,如果 `nums[i]` 小于等于 `n`,则说明该数字没有出现在原数组中，我们将它加一后加入结果数组 `result` 中。

  3. 最后，我们返回结果数组 `result`,其中包含了所有在区间 [1, n] 范围内但没有出现在原数组中的数字。

需要注意的是，该函数的时间复杂度为 O(n),空间复杂度为 O(1)。

 三、解题方法二
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1) % n
            nums[x] += n
        return [i + 1 for i in range(n) if nums[i] <= n]
这个解题方法使用了哈希表来记录每个数字出现的次数。具体来说，我们首先定义一个类 Solution,并在其中实现一个名为 findDisappearedNumbers 的方法。该方法接受一个整数数组 nums 作为参数，返回一个整数列表，其中包含了所有在区间 [1, n] 范围内但没有出现在原数组中的数字。

在方法中，我们首先获取输入数组 nums 的长度 n,并定义一个变量 x。对于每个数字 num,我们将其减去 1 并对数组长度取模，得到的结果即为它在原数组中应该出现的位置。然后，我们将该位置的元素加上数组长度，这样就可以将原本在该位置出现的数字变为不在数组中的状态。具体来说，假设原数组中第 i 个位置的元素为 a[i],则经过上述操作后，a[i] - n 就会变成一个负数，表示该数字已经不在原数组中了。

接下来，我们使用一个循环来遍历整个数组 nums,对于每个下标 i,如果 nums[i] 小于等于 n,则说明该数字没有出现在原数组中。为了判断一个数字是否出现过，我们需要检查哈希表中对应的键值是否大于零。因此，我们在哈希表中查找键值为 nums[i] 的项，如果找到了且其值大于零，则说明该数字已经出现过了；否则，说明该数字没有出现过。最后，我们将所有没有出现过的数字加入结果列表中，并返回结果列表。

四、方法的区别 
这两种解题方法的主要区别在于实现方式和时间复杂度。

第一种方法使用了数组来记录每个数字出现的次数，并通过遍历数组来查找所有没有出现在原数组中的数字。该方法的时间复杂度为 O(n),空间复杂度为 O(1)。

第二种方法使用了哈希表来记录每个数字出现的次数，并通过遍历哈希表来查找所有没有出现在原数组中的数字。该方法的时间复杂度也为 O(n),但由于哈希表的查找操作是常数级别的，因此空间复杂度为 O(n)。

在实际应用中，如果输入数组的大小比较小，那么两种方法的时间复杂度差异不大，可以选择任意一种；如果输入数组的大小比较大，那么第二种方法的空间复杂度会比第一种方法高，因此可能会导致内存不足的问题。在这种情况下，可以考虑使用第一种方法来解决问题。