打卡力扣题目十三

举报
踏破千重浪 发表于 2023/08/14 20:21:44 2023/08/14
【摘要】 目录 一、问题二、解题方法一 三、解题方法二四、方法的区别  关于 ARTS 的释义 —— 每周完成一个 ARTS:● Algorithm: 每周至少做一个 LeetCode 的算法题● Review: 阅读并点评至少一篇英文技术文章● Tips: 学习至少一个技术技巧● Share: 分享一篇有观点和思考的技术文章希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。 ...

目录

 一、问题

二、解题方法一

 三、解题方法二

四、方法的区别 

 关于 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)。

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。