First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given[1,2,0]
return3
,
and[3,4,-1,1]
return2
.
Your algorithm should run inO(n) time and uses constant space.
这条题目虽然简单,但是思路还是很多的,可以开拓一下思路。
下面三种思路都是O(n)时间复杂度,测试运行时间基本上都没区别:
1 排序之后查找
2 把出现的数值放到与下标一致的位置,再判断什么位置最先出现不连续的数值,就是答案了。
3 和2差不多,把出现过的数值的下标位置做好标识,如果没有出现过的数组的下标就没有标识,那么这个就是答案。
第一个思路最简单了:
class Solution {
public:
int firstMissingPositive(int A[], int n) {
sort(A, A+n);
int res = 0;
int i = 0;
while (i<n && A[i]<=0) i++;
for (; i < n; i++)
{//注意:一看到序列就应该马上反应问题:是否有重复元素???
if (i>0 && A[i] == A[i-1]) continue;
if (A[i] - res != 1) return res+1;
else res = A[i];
}
return res+1;
}
};
下面是参考了leetcode上的程序,思路2:
http://discuss.leetcode.com/questions/219/first-missing-positive
int firstMissingPositive2(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])不用那么多条件就可以了。
//因为只要是已经到位了的元素即:A[i]-1==i了,那么判断如果有重复元素
//两个位置交换就最好考虑好两个位置出现的可能情况。考虑问题全面,两个条件都考虑好。
//update:增加i!=A[i]表示i位置没到位,A[A[i]-1] != A[i]表示A[i]-1位置没到位,两个位置都判断也很好的。
if (A[A[i]-1] != A[i])
{
swap(A[A[i]-1], A[i]);
i--;
}
}
}
for (int j=0; j<n; ++j)
if (A[j]-1 != j)
return j+1;
return n+1;
}
也是思路二,不过上面的是处理下标从1开始,下面的程序是处理下标从0开始的:
int firstMissingPositive3(int A[], int n) {
int i = 0;
while (i < n) {
//逐个把A[i]放到A[i]位置的思想
//1:找到一个A[i]是在0到n范围的就放到相应位置
//2:没找到的直接跳过
//简单来说:就是把数字与下标对应起来
if (A[i] >= 0 && A[i] < n && A[A[i]] != A[i])
swap(A[i], A[A[i]]);
else i++;
}
int k = 1;
while (k < n && A[k] == k) k++;
if (n == 0 || k < n) return k;
else return A[0] == k ? k + 1 : k;
}
思路三,好像稍微复杂一点。
int firstMissingPositive4(int A[], int n) {
if(n <= 0)
return 1;
int intOutOfRange = n + 2;
//first run, turn every negetive value into an impossible positive value
//make every value in A is positive
for(int i = 0 ; i < n ; ++ i) {
if(A[i] <= 0)
A[i] = intOutOfRange;
}
//second run, make A[] as a hash table, A[i] indicate the presence of i + 1
//the way is that, if k in [1,n] is in A[], then turn A[k -1] to negetive
for(int i = 0 ; i < n ; ++i) {
int ai = A[i];
int absi = abs(ai);
if(absi <= n)
A[absi-1] = -abs(A[absi-1]);
}
//third run, if A[i] is positive, from step 2, we know that i + 1 is missing.
for(int i = 0 ; i < n ; ++i) {
if(A[i] > 0)
return i + 1;
}
//all int from 1 to n is present, then return n + 1
return n+1;
}
简单:
//2014-1-27 update
int firstMissingPositive(int A[], int n)
{
for (int i = 0; i < n; )
{
if (0<A[i]&& A[i]<n && A[i] != i && A[A[i]] != A[i])
swap(A[i], A[A[i]]);
else i++;
}
for (int i = 1; i < n; i++)
if (A[i] != i) return i;
return A[0] == n? n+1:n;
}
分享到:
相关推荐
leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 SDE。 (只有简单和中等的问题) leetcode 10 - 正则表达式匹配(难) ...
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 │ ├── 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 ...
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...
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_...
lru缓存leetcode 哦,我的 Leetcode Leetcode 题解 **第 0000 题:**二的幂 给定一个整数,编写一个函数来确定它是否是 2 的幂。 **第 0001 题:**1 位的数量 编写一个函数,该函数接受一个无符号整数并返回它具有的...
缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists....
leetcode 2 code_interview leetcode和lintcode的一些题目的解法 是剑指offer 是面试中遇到的有意思的题目总结,比如说BAT,intel,NVIDIA等公司面试的题目记录 ...41-first-missing-positive 01-Two-Sum 求解第K
股票买卖最佳时机leetcode Java项目 这是 ...First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。 数组...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 ...