LeetCode 41. 缺失的第一个正数

作者:神秘网友 发布时间:2021-02-22 19:20:12

LeetCode 41. 缺失的第一个正数

新手学习中,有任何错误或者更好地方法、思路欢迎指教!


#Array 6

题目难度:困难

题目描述:

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

进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗

示例 1:
输入:nums = [1,2,0]
输出:3
示例 2: 输入:nums = [3,4,-1,1] 输出:2
示例 3: 输入:nums = [7,8,9,11,12] 输出:1 提示: 0 = nums.length = 300 -231 = nums[i] = 231 - 1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/first-missing-positive 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

1. 山路十八弯解法:

思路:
遍历数组,判断missing是否出现过,没出现过则count++。
当count等于数组长度时代表数组中没有该missing值,返回missing;否则missing++继续下一轮数组遍历。
max为数组中的最大值,作为循环跳出的条件。

class Solution { public int firstMissingPositive(int[] nums) { int missing = 1; //没有出现的最小的正整数 int max = 0; //数组中的最大值(注意要赋初值!!!) int count; //数组中不与missing重复的数的个数 if (nums.length 0){ max = nums[0]; do{ count = 0; for (int i = 0; i nums.length; i++){ //遍历数组,判断missing是否出现过 if (nums[i] == missing){ continue; } else { count++; } if (nums[i] max){ //查找数组中的最大值 max = nums[i]; } } if (count == nums.length) { //当数组中没有与missing重复的数时(missing未出现) return missing; } else missing++; } while (missing = max); } return missing; } }

LeetCode 41. 缺失的第一个正数 相关文章

  1. leetcode 8. String to Integer (atoi)

    题目链接 https://leetcode-cn.com/problems/string-to-integer-atoi/ 截取字符然后乘10操作即可,坑点在于溢出判断,可以用MAX_INT/10与该数比较。 自己写的代码比较蠢,有漏洞,但数据可能比较水所以过了。官方题解是自动机,学会了再来写。。 class Solut

  2. Leetcode92. 反转链表 II

    92. 反转链表 II Difficulty: 中等 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1-2-3-4-5-NULL, m = 2, n = 4输出: 1-4-3-2-5-NULL Solution Language: java ?/** * Definition for singly-linked li

  3. Medium | LeetCode 11. 盛最多水的容器 | 双指针

    11. 盛最多水的容器 给你 n 个非负整数 a1,a2,...,a``n ,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明: 你不

  4. LeetCode 76. Minimum Window Substring

    题目描述 题目链接 思路 滑动窗口 + 欠账表 将目标字符串加入到一个欠账表中,这个欠帐表记录了目标字符串中每个字符出现的次数,因为题目说到字符串都是英文字母,所以定义一个256大小的字符数组即可 // 初始化欠帐表// 如果不止ASCII码的字符,则可以用Has

  5. LeetCode - Minimum Add to Make Parentheses Valid

    Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.Formally, a parentheses string is valid if and only if:It is the e

  6. 【LeetCode】766. 托普利茨矩阵

    题目链接:https://leetcode-cn.com/problems/toeplitz-matrix/ (BFS写魔怔了,看啥都想用BFS解决,这题其实只需要简单遍历即可,当然用BFS也没问题) 方法一:BFS 由于题目要求矩阵上每一条由左上到右下的对角线上的元素都相同,所以可以使用BFS从右上角的

  7. leetcode 404,530,543,563,572,589,617,637,700

    404 按理说也可以递归做。 public static int sumOfLeftLeaves(TreeNode root) { int total = 0; LinkedListTreeNode stack = new LinkedList(); stack.push(root); while (!stack.isEmpty()){ TreeNode pop = stack.pop(); TreeNode left = pop.left; if (l

  8. Leetcode 766 托普利茨矩阵

    题目定义: 给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵,返回 true ;否则,返回 false 。如果矩阵上每一条由左上到右下的对角线上的元素都相同,那么这个矩阵是 托普利茨矩阵 。示例 1:[1,2,3,4][5,1,2,3][9,5,1,2]输入:matrix = [[1,2,

  9. 1.两数之和【数组】

    1.LeetCode地址:两数之和 2.题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标。 示例 1:输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] =

  10. LeetCode刷题之路-697. 两数相加

    LeetCode刷题之路-697. 两数相加 题目介绍 给定一个非空且只包含非负数的整数数组 nums ,数组的度的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。 示例 1: 输入:[1, 2, 2,

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词