原题链接:http://oj.leetcode.com/problems/first-missing-positive/这道题要求用线性时间和常量空间,思想借鉴到了Counting sort中的方法,不了解的朋友可以参见Counting
sort - Wikipedia。既然不能用额外空间,那就只有利用数组本身,跟Counting sort一样,利用数组的index来作为数字本身的索引,把正数按照递增顺序依次放到数组中。即让A[0]=1, A[1]=2, A[2]=3,
... , 这样一来,最后如果哪个数组元素违反了A[i]=i+1即说明i+1就是我们要求的第一个缺失的正数。对于那些不在范围内的数字,我们可以直接跳过,比如说负数,0,或者超过数组长度的正数,这些都不会是我们的答案。代码如下:
public int firstMissingPositive(int[] A) {
if(A==null || A.length==0)
{
return 1;
}
for(int i=0;i<A.length;i++)
{
if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i])
{
int temp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = temp;
i--;
}
}
for(int i=0;i<A.length;i++)
{
if(A[i]!=i+1)
return i+1;
}
return A.length+1;
}
实现中还需要注意一个细节,就是如果当前的数字所对应的下标已经是对应数字了,那么我们也需要跳过,因为那个位置的数字已经满足要求了,否则会出现一直来回交换的死循环。这样一来我们只需要扫描数组两遍,时间复杂度是O(2*n)=O(n),而且利用数组本身空间,只需要一个额外变量,所以空间复杂度是O(1)。这道题个人还是比较喜欢的,既有一点算法思想,在实现中又有一些注意细节,而且整体来说模型比较简单,很适合在面试中出现。
分享到:
相关推荐
leetcode 71 Python用 ...Missing Positive (HARD) leetcode 42. 收集雨水 (HARD) leetcode 44. 通配符匹配 (HARD) leetcode 45. Jump Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-
├── First Missing Positive │ ├── Readme.md │ └── solution.js ├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── ...
leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack ...
缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists....
First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85...
268| [Missing Number](https://leetcode.com/problems/missing-number/) | [C++](./C++/missing-number.cpp) [Python](./Python/missing-number.py) | _O(n)_ | _O(1)_ | Medium | LintCode || 318| [Maximum ...
题:**First Missing Positive 给定一个未排序的整数数组,找到第一个缺失的正整数。 例如,给定 [1,2,0] 返回 3,而 [3,4,-1,1] 返回 2。 您的算法应该在 O(n) 时间内运行并使用恒定空间。 **第 0003 题:**String ...
leetcode 2 code_interview leetcode和lintcode的一些题目的解法 是剑指offer 是面试中遇到的有意思的题目总结,比如说BAT,intel,NVIDIA等公司面试的题目记录 ...41-first-missing-positive 01-Two-Sum 求解第K
41_First_Missing_Positive 299_Bulls_and_Cows 134_Gas_Station 118_Pascal's_Triangle_I 119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_...
股票买卖最佳时机leetcode Java项目 这是 ...First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
buy-and-sell-stock-ii/ https://leetcode.com/problems/maximum-subarray/ https://leetcode.com/problems/first -missing-positive / https://leetcode.com/problems/container-with-most-water/ htt
First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search in Rotated Sorted Array Search in Rotated Sorted Array II ...