文章目錄

• • 1. 題目信息
  • 2. 思路
  • 3. 代碼

1. 題目信息

給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。

示例 1:輸入: [1,2,0] 輸出: 3 示例 2:輸入: [3,4,-1,1] 輸出: 2 示例 3:輸入: [7,8,9,11,12] 輸出: 1

說明:
你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)，并且只能使用常數(shù)級(jí)別的空間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/first-missing-positive
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 思路

• 先找出最大值，O(n)
• i 從1到最大值開始查找，找到了就 i+1，沒找到就返回 i，O(n)復(fù)雜度

3. 代碼

class Solution { public:int firstMissingPositive(vector<int>& nums) {int i, maxNum = INT_MIN;for(i = 0; i < nums.size(); ++i){if(nums[i] > maxNum)maxNum = nums[i];}for(i = 1; i <= maxNum; ++i){if(find(nums.begin(), nums.end(), i) == nums.end())return i;}return i;} };

or
只考慮1到n的數(shù)字，應(yīng)該使得 nums[i] = i+1

class Solution { public:int firstMissingPositive(vector<int>& nums) {int i, n = nums.size();for(i = 0; i < nums.size(); ++i){while(nums[i]>0 && nums[i] <= n && nums[nums[i]-1] != nums[i])swap(nums[i], nums[nums[i]-1]);}for(i = 0; i < nums.size(); ++i){if(nums[i] != i+1)return i+1;}return n+1;} }; class Solution:# py3def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):while nums[i]>0 and nums[i]<=n and nums[i] != nums[nums[i]-1]:t = nums[nums[i]-1]nums[nums[i]-1] = nums[i]nums[i] = ti = 0while i < n:if nums[i] != i+1:return i+1i += 1return i+1

總結(jié)

以上是生活随笔為你收集整理的LeetCode 41. 缺失的第一个正数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。