LeetCode 41 缺失的第一个正数

这篇具有很好参考价值的文章主要介绍了LeetCode 41 缺失的第一个正数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

输入:nums = [1,2,0]
输出:3

示例 2:

输入:nums = [3,4,-1,1]
输出:2

示例 3:

输入:nums = [7,8,9,11,12]
输出:1

提示:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

解法

如果本题没有额外的时空复杂度要求,那么就很容易实现:

  • 我们可以将数组所有的数放入哈希表,随后从 111 开始依次枚举正整数,并判断其是否在哈希表中;
  • 我们可以从 111 开始依次枚举正整数,并遍历数组,判断其是否在数组中。

如果数组的长度为 N,那么第一种做法的时间复杂度为 O(N),空间复杂度为 O(N);第二种做法的时间复杂度为 O(N^2),空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N) 且空间复杂度为 O(1)

但是我们可以利用给定数组中的空间来存储一些状态。也就是说,如果题目给定的数组是不可修改的,那么就不存在满足时空复杂度要求的算法;但如果我们可以修改给定的数组,那么是存在满足要求的算法的。

对于上面中提到的第一种做法:

我们可以将数组所有的数放入哈希表,随后从 111 开始依次枚举正整数,并判断其是否在哈希表中。

仔细想一想,我们为什么要使用哈希表?这是因为哈希表是一个可以支持快速查找的数据结构:给定一个元素,我们可以在 O(1)的时间查找该元素是否在哈希表中。因此,我们可以考虑将给定的数组设计成哈希表的「替代产品」。

**实际上,对于一个长度为 N 的数组,其中没有出现的最小正整数只能在 [1,N+1] 中。**这是因为如果 [1, N] 都出现了,那么答案是 N+1,否则答案是 [1,N] 中没有出现的最小正整数。

这样一来,我们将所有在 [1, N]范围内的数放入哈希表,也可以得到最终的答案。而给定的数组恰好长度为 N,这让我们有了一种将数组设计成哈希表的思路:

我们对数组进行遍历,对于遍历到的数 x,如果它在[1,N] 的范围内,那么就将数组中的第 x−1个位置(注意:数组下标从 0开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是 N+1,否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢?由于数组中的数没有任何限制,因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质:由于我们只在意 [1, N] 中的数,因此我们可以先对数组进行遍历,把不在 [1, N] 范围内的数修改成任意一个大于 N 的数(例如 N+1)。这样一来,数组中的所有数就都是正数了,因此我们就可以将「标记」表示为「负号」。算法的流程如下:

  • 我们将数组中所有小于等于 0 的数修改为 N+1;
  • 我们遍历数组中的每一个数 x,它可能已经被打了标记,因此原本对应的数为 |x|,其中 | | 为绝对值符号。如果 ∣x∣∈[1,N],那么我们给数组中的第 |x| - 1 个位置的数添加一个负号。注意如果它已经有负号,不需要重复添加;
  • 在遍历完成之后,如果数组中的每一个数都是负数,那么答案是 N+1,否则答案是第一个正数的位置加 1。

LeetCode 41 缺失的第一个正数,# leetcode,leetcode,算法,数据结构

java代码:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将负数变为n + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 将元素<=n对应的位置变为负数,表示在该位置的元素在1 ~ n范围内
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <=  n) {
                // 注意由于有相同的元素,有可能原来nums[num - 1]的元素由正数变负数,然后又变为正数,所以使用绝对值的负数
                nums[num - 1] = - Math.abs(nums[num - 1]);
            }
        }
        // 返回第一个大于0的元素下标 + 1
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

复杂度文章来源地址https://www.toymoban.com/news/detail-798180.html

  • 时间复杂度:O(N),其中 N 为数组的长度
  • 空间复杂度:O(1)

到了这里,关于LeetCode 41 缺失的第一个正数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode】缺失的第一个正数 hashmap

    先把数组里面的正数i都取出来,放到对应的arr[i]=1 然后遍历arr,如果不为1,那么就返回i

    2024年01月19日
    浏览(38)
  • 41. 缺失的第一个正数 --力扣 --JAVA

    给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 对数组进行排序,便于查看是否连续; 因为是最小正整数,所以判断值应从1开始; 只要当前元素值大于最小值,则直接返回最

    2024年02月06日
    浏览(48)
  • 力扣数组类题目--41缺失的第一个正数

    41 缺失的第一个正数 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案 。 示例 1: 输入:nums = [1,2,0] 输出:3 示例 2: 输入:nums = [3,4,-1,1] 输出:2 示例 3: 输入:nums = [7,8,9,11,12

    2024年02月11日
    浏览(38)
  • Practices11|41. 缺失的第一个正数(数组)、73. 矩阵置零(矩阵)

    1.题目: 给你一个未排序的整数数组  nums  ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为  O(n)  并且只使用常数级别额外空间的解决方案。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 5 * 105 -231 = nums[i] = 231 - 1 2.思路: 如果本题没有额外的时空复杂

    2024年02月12日
    浏览(34)
  • 算法---缺失的第一个正数

    给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 借用map 就可以实现,但是如果不借用map,在原空间上,也可以实现,不过想要使用原来的数据,会有侵略性,会把原来的数据修改掉。 方法一: 方法二: 算法是很看一个人的思维逻辑的,所以很多

    2024年02月06日
    浏览(37)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(53)
  • LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

    在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums ,和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target ,返回 [-1, -1] 。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此

    2024年02月02日
    浏览(47)
  • 【LeetCode】917. 仅仅反转字母、387. 字符串中的第一个唯一字符

     作者:小卢   专栏:《Leetcode》 喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》 目录  917. 仅仅反转字母  387. 字符串中的第一个唯一字符 917. 仅仅反转字母  题目描述: 给你一个字符串  s  ,根据下述规则反转

    2023年04月12日
    浏览(62)
  • (链表) 剑指 Offer 52. 两个链表的第一个公共节点 ——【Leetcode每日一题】

    难度:简单 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则

    2024年02月15日
    浏览(53)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包