【题目】
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.
【分析】
类似于桶排序。
每当A[i] != i+1时,即A[i]不在正确的位置上,需要交换到排序数组中他相应的位置上去。
交换A[i]与A[A[i]-1],直到无法交换。
【代码】
/*********************************
* 日期:2015-01-13
* 作者:SJF0115
* 题目: 41.First Missing Positive
* 来源:https://oj.leetcode.com/problems/first-missing-positive/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
using namespace std;
class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(A == NULL || n <= 0){
return 1;
}//if
// 交换到在排序数组中应有的位置
for(int i = 0;i < n;i++){
// 交换直到不能交换
while(A[i] != i+1){
// 是否需要交换
if(A[i] <= 0 || A[i] > n || A[i] == i+1 || A[i] == A[A[i]-1]){
break;
}//if
// 交换
int tmp = A[i];
A[i] = A[tmp-1];
A[tmp-1] = tmp;
}//while
}//for
// First Missing Positive
for(int i = 0;i < n;i++){
if(A[i] != i+1){
return i+1;
}//if
}//for
return n+1;
}
};
int main(){
Solution solution;
int A[] = {1,1};
cout<<solution.firstMissingPositive(A,2)<<endl;
return 0;
}
【分析二】
题目的最后一行,要求O(n)实际上暗示了用hash,但是又说要contant space,就没法再开新空间来建hash。
正好这个题目中处理的是1到n的数据,提供了一个将输入的数组同时用作hash表的可能性。
于是算法就是:
-
第一遍扫描排除所有非正的数,将它们设为一个无关紧要的正数(n+2),因为n+2不可能是答案
-
第二遍扫描,将数组作为hash表来使用,用数的正负来表示一个数是否存在在A[]中。
当遇到A[i],而A[i]属于区间[1,n],就把A中位于此位置A[i] – 1的数置翻转为负数。
所以我们取一个A[i]的时候,要取它的abs,因为如果它是负数的话,通过步骤一之后,只可能是我们主动设置成负数的
-
第三遍扫描,如果遇到一个A[i]是正数,说明i+1这个数没有出现在A[]中,只需要返回即可。
-
上一步没返回,说明1到n都在,那就返回n+1
【代码二】
class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(A == NULL || n <= 0){
return 1;
}//if
int impossValue = 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] = impossValue;
}//if
}//for
//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 value = abs(A[i]);
if(value <= n){
A[value-1] = -abs(A[value-1]);
}//if
}//for
//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;
}//if
}//for
//all int from 1 to n is present, then return n + 1
return n+1;
}
};
分享到:
相关推荐
leetcode 71 Python用 Python ...Positive (HARD) leetcode 42. 收集雨水 (HARD) leetcode 44. 通配符匹配 (HARD) leetcode 45. Jump Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-
41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain ...
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 ...
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 ...
收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。 数组...missing-positive / https://leetcode.com/problems/container-with-most-water/ htt
├── First Missing Positive │ ├── Readme.md │ └── solution.js ├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── ...
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_...
缺失的第一个整数](./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 给定一个未排序的整数数组,找到第一个缺失的正整数。 例如,给定 [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
股票买卖最佳时机leetcode Java项目 这是 ...First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
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 ...