首页 > 代码库 > Leetcode First Missing Positive
Leetcode First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
给定无序整型数组，找出第一个不在数组里的正整数，要求时间复杂度为O(n),空间复杂度为O(1)
本题使用数组下标来存储相应的值，比如第k个元素（对应的下标是k-1）存储数字k，也就是A[k-1] = k。
对于大于数组长度的数字或者小于1的数字直接抛弃
一旦有了新数组，就从头开始扫描，遇到第一个A[k-1]不等于k时，输出k，如果没有遇到，那结果只能是数组长度的下一个数
class Solution {public: int firstMissingPositive(int A[], int n) { for(int i = 0 ; i < n; ++ i){ if(A[i] > 0 && A[i]<=n){ if(A[i]-1 != i && A[A[i]-1]!=A[i]) { swap(A[i],A[A[i]-1]); i--; } } } for(int i = 0 ; i < n; ++ i) if(A[i]-1 != i) return i+1; return n+1; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。