Leetcode41缺失的第一个正数

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

Leetcode41缺失的第一个正数,算法,算法

思路:原地哈希表

长度为N的数组,没有出现过的正整数一定是1~N+1中的一个。

此时会思考能不能用一个哈希表来保存出现过的1~N+1的数,然后从 1 开始依次枚举正整数,并判断其是否在哈希表中

但是题目要求常数级别的空间,就不能使用N的哈希表了。

这里将原数组当做哈希表,使用标记的办法来标记出现过的正整数,最后遍历数组,第一个没出现的下标+1就是答案

怎么样进行标记呢?

  • 先遍历一遍数组,将非正整数置为N+1
  • 再遍历一遍数组,将1~N正整数对应的下标位置置为负数
  • 最后遍历一遍数组,第一个不是负数的位置i+1就是没出现过的最小的正整数

 文章来源地址https://www.toymoban.com/news/detail-745020.html

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for(int i = 0;i<len;i++){
            if(nums[i]<=0){
                nums[i] = len+1;
            }
        }
        for(int i = 0;i<len;i++){
            int num = Math.abs(nums[i]);
            if(num<=len&&num>0){
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }
        for(int i = 0;i<len;i++){
            if(nums[i]>=0){
                return i+1;
            }
        }
        return len+1;
    } 
}

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

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

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

相关文章

  • 41. 缺失的第一个正数 --力扣 --JAVA

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

    2024年02月06日
    浏览(46)
  • 力扣数组类题目--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日
    浏览(36)
  • Practices11|41. 缺失的第一个正数(数组)、73. 矩阵置零(矩阵)

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

    2024年02月12日
    浏览(33)
  • 【leetcode】缺失的第一个正数 hashmap

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

    2024年01月19日
    浏览(35)
  • 算法---缺失的第一个正数

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

    2024年02月06日
    浏览(37)
  • 【算法】编写一个函数,返回两个正数的和,有可能超过ulong长度

    编写一个函数,返回两个数字的和。输入数字是字符串,函数必须返回一个字符串。 示例: 添加(“123”,“321”);-“444” 添加(“11”,“99”);-“110” 备注: 输入的数字很大,有可能超过ulong长度。 输入是一个只有数字的字符串。 数字是正数。     算法实现:

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

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

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

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

    2023年04月12日
    浏览(58)
  • (链表) 剑指 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日
    浏览(51)
  • 算法训练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日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包