LeetCode - 41. First Missing Positive

本文主要是介绍LeetCode - 41. First Missing Positive，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

41. First Missing Positive

Problem's Link

----------------------------------------------------------------------------

Mean:

给你一组整数，找出第一个空缺的正整数.

要求：时间O(n),空间O(n).

analyse:

这题时间O(n)想了半天没想到，用O(n*logn)过的.

然后看了discuss，想法非常巧妙，自愧不如.

Time complexity: O(N)

view code

 /** 
  * ----------------------------------------------------------------- 
  * Copyright (c) 2016 crazyacking.All rights reserved. 
  * ----------------------------------------------------------------- 
  *       Author: crazyacking 
  *       Date  : 2016-03-05-18.56 
  */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 using namespace std; 
 typedef long long( LL); 
 typedef unsigned long long( ULL); 
 const double eps( 1e-8); 
 
 class Solution 
 { 
 public : 
     vector < vector < int >> combinationSum2( vector < int >& candidates , int target) 
     { 
         sort( candidates . begin (), candidates . end()); 
         vector < vector < int >> res; 
         vector < int > combination; 
         combinationSum( candidates , res , combination , target , 0); 
         return res; 
     } 
 private : 
     void combinationSum( vector < int >& candidates , vector < vector < int >> & res , vector < int >& combination , int target , int begin) 
     { 
         if( ! target) 
         { 
             res . push_back( combination); 
             return; 
         } 
         for( int i = begin; target >= candidates [ i ] && i < candidates . size() ; ++ i) 
         { 
             if( i == begin || candidates [ i ] != candidates [ i - 1 ]) 
             { 
                 combination . push_back( candidates [ i ]); 
                 combinationSum( candidates , res , combination , target - candidates [ i ], i + 1); 
                 combination . pop_back(); 
             } 
         } 
         return; 
     } 
 }; 
 
 
 int main() 
 { 
     freopen( "H: \\ Code_Fantasy \\ in.txt" , "r" , stdin); 
     int n , target; 
     while( cin >>n >> target) 
     { 
         cout <<n << " " << target << endl; 
         vector < int > ve; 
         for( int i = 0; i <n; ++ i) 
         { 
             int tmp; 
             cin >> tmp; 
             ve . push_back( tmp); 
         } 
         Solution solution; 
         vector < vector < int >> ans = solution . combinationSum2( ve , target); 
         for( auto p1: ans) 
         { 
             for( auto p2: p1) 
             { 
                 cout << p2 << " "; 
             } 
             cout << endl; 
         } 
     } 
     return 0; 
 } 
 /* 
 
 */ 

O(n)时间，O(1)空间的代码：

 class Solution { 
 public : 
     int firstMissingPositive( vector < int >& nums) { 
         int n = nums . size(); 
         for ( int i = 0; i < n; i ++) 
             while ( nums [ i ] > 0 && nums [ i ] <= n && nums [ nums [ i ] - 1 ] != nums [ i ]) 
                 swap( nums [ i ], nums [ nums [ i ] - 1 ]); 
         for ( int i = 0; i < n; i ++) 
             if ( nums [ i ] != i + 1) 
                 return i + 1; 
         return n + 1; 
     } 
 }; 