吴忠网站建设哪家好,苏州园区房价,软件技术属于什么学类,免费推广网址的方法leetcode41. 缺失的第一个正数
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1#xff1a;
输入#xff1a;nums [1,2,0] 输出#xff1a;3 解释#xf…leetcode41. 缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入nums [1,2,0] 输出3 解释范围 [1,2] 中的数字都在数组中。 示例 2
输入nums [3,4,-1,1] 输出2 解释1 在数组中但 2 没有。 示例 3
输入nums [7,8,9,11,12] 输出1 解释最小的正数 1 没有出现。 目录 leetcode41. 缺失的第一个正数题目分析算法介绍算法步骤算法流程算法代码算法分析相似题目 题目分析
这是一个关于数组处理的问题。题目要求实现一个函数firstMissingPositive该函数接受一个整数数组nums并返回数组中第一个缺失的正整数。
算法介绍
为了解决这个问题我们可以使用一种特殊的标记方法。首先我们将所有小于等于0的元素替换为n1其中n是数组的长度。然后我们遍历数组将每个元素的正负号反转如果它是一个正数。通过这种方式我们可以标记数组中出现的所有正整数。最后我们再次遍历数组找到第一个未标记的正整数即为答案。
算法步骤
遍历数组nums将所有小于等于0的元素替换为n1。再次遍历数组nums反转每个元素的正负号如果它是一个正数。第三次遍历数组nums找到第一个未标记的正整数即为答案。
算法流程 #mermaid-svg-4TXeoEyZ4fbWydkn {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .error-icon{fill:#552222;}#mermaid-svg-4TXeoEyZ4fbWydkn .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-4TXeoEyZ4fbWydkn .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-4TXeoEyZ4fbWydkn .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-4TXeoEyZ4fbWydkn .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-4TXeoEyZ4fbWydkn .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-4TXeoEyZ4fbWydkn .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-4TXeoEyZ4fbWydkn .marker{fill:#333333;stroke:#333333;}#mermaid-svg-4TXeoEyZ4fbWydkn .marker.cross{stroke:#333333;}#mermaid-svg-4TXeoEyZ4fbWydkn svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-4TXeoEyZ4fbWydkn .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .cluster-label text{fill:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .cluster-label span{color:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .label text,#mermaid-svg-4TXeoEyZ4fbWydkn span{fill:#333;color:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .node rect,#mermaid-svg-4TXeoEyZ4fbWydkn .node circle,#mermaid-svg-4TXeoEyZ4fbWydkn .node ellipse,#mermaid-svg-4TXeoEyZ4fbWydkn .node polygon,#mermaid-svg-4TXeoEyZ4fbWydkn .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-4TXeoEyZ4fbWydkn .node .label{text-align:center;}#mermaid-svg-4TXeoEyZ4fbWydkn .node.clickable{cursor:pointer;}#mermaid-svg-4TXeoEyZ4fbWydkn .arrowheadPath{fill:#333333;}#mermaid-svg-4TXeoEyZ4fbWydkn .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-4TXeoEyZ4fbWydkn .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-4TXeoEyZ4fbWydkn .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-4TXeoEyZ4fbWydkn .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-4TXeoEyZ4fbWydkn .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-4TXeoEyZ4fbWydkn .cluster text{fill:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn .cluster span{color:#333;}#mermaid-svg-4TXeoEyZ4fbWydkn div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-4TXeoEyZ4fbWydkn :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 开始 初始化 n 遍历 nums 替换小于等于0的元素为 n1 遍历 nums 反转每个元素的正负号 如果它是一个正数 遍历 nums 找到第一个未标记的正整数 返回找到的正整数 结束 算法代码
class Solution {
public:int firstMissingPositive(vectorint nums) {int n nums.size();for (int num: nums) {if (num 0) {num n 1;}}for (int i 0; i n; i) {int num abs(nums[i]);if (num n) {nums[num - 1] -abs(nums[num - 1]);}}for (int i 0; i n; i) {if (nums[i] 0) {return i 1;}}return n 1;}
};算法分析
时间复杂度O(n)其中n是数组nums的长度。我们只需要遍历数组三次。空间复杂度O(1)因为除了输入数组外我们只使用了常数个额外空间。易错点 确保正确地将所有小于等于0的元素替换为n1。在反转正负号时确保只对正数进行操作。
相似题目
题目链接缺失的第一个正数LeetCode 41缺失的数字LeetCode 268
请注意以上表格仅为示例实际链接可能需要根据具体平台和题目编号进行调整。
