給定一個未排序的整數陣列，找出其中沒有出現的最小的正整數，
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說明:
你的演算法的時間復雜度應為O(n)，并且只能使用常數級別的空間，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/first-missing-positive
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& nums) { 4 //這是看了解答后的代碼 滿足題意 但速度沒提高太多 5 int size = nums.size(); 6 7 int *numsHash; 8 int size_hash = size +1; 9 10 //創建一個哈希表 初始化為011 numsHash = new int[size_hash]();12 //遍歷nums 對于小于陣列長度的元素在哈希表中打個標記13 //對于比陣列長度大的資料可以忽略，因為第一個缺失的正數沒這么大14 for (int i = 0; i < size; ++i)15 {16 if (nums[i] > 0 && nums[i] < size_hash)17 {18 numsHash[nums[i]] = 1;19 } 20 }21 22 //遍歷哈希表 找出第一個沒打標記的23 int *end_pos = numsHash + size_hash;24 for (int *p = numsHash + 1; p != end_pos; ++p)25 {26 if (*p == 0)27 {28 return p - numsHash;29 }30 }31 32 return size_hash;33 }34 35 int firstMissingPositiveNew(vector<int>& nums) {36 37 //這是我自己想的答案，不符合題目O(n)要求，但排名也挺高38 //排序 然后找出第一個大于0的數字39 //順序查找下去，直到發現本元數比上一個元素大1就說明找到了40 sort(nums.begin(), nums.end());執行結果：通過顯示詳情執行用時 :4 ms, 在所有 cpp 提交中擊敗了83.16%的用戶記憶體消耗 :8.7 MB, 在所有 cpp 提交中擊敗了73.72%的用戶
//從1開始找出第一個不在陣列里面的正數 慢41 //for (int i = 1; i <= INT_MAX; ++i)42 //{43 // if (!binary_search(nums.begin(), nums.end(), i))44 // {45 // return i;46 // }47 //}48 49 auto it = upper_bound(nums.begin(), nums.end(), 0);50 51 if (it == nums.end() || *it != 1) return 1;52 53 for (++it; it != nums.end(); ++it)54 {55 if ((*it - *(it - 1)) > 1)56 {57 return *(it - 1) + 1;58 }59 }60 61 return *(it - 1) + 1;62 }63 };
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86641.html
標籤：C++