問題描述
給你一個未排序的整數陣列 nums ，請你找出其中沒有出現的最小的正整數，
示例 1：
輸入：nums = [1,2,0]
輸出：3
示例 2：
輸入：nums = [3,4,-1,1]
輸出：2
示例 3：
輸入：nums = [7,8,9,11,12]
輸出：1
提示：
0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1
解題思路：
若有時間復雜度和空間負責度的要求，則解題相當的困難，如果不做要求的話，本題可以將時間復雜度和空間復雜度降低到時間復雜度不超過O(nlogn),空間復雜度O(n).
我們首先將陣列中的正整數都收集起來，然后對陣列中的正整數排序(這里可以直接借助TreeSet集合)，
如果正整數陣列中最前面的元素大于1，那么缺失的第一個正數為1
否則的話，我們就從1開始逐個嘗試陣列中是否存在從1開始遞增的正整數，如果某個正整數缺失的話，就直接回傳，如果一直找到陣列的末尾都沒有找到，就回傳最后一個元素值加1，當然，這里還有一個重要的前提就是，保持正整數陣列中無重復元素，我們可以借助set集合
代碼實作：
class Solution {
public int firstMissingPositive(int[] nums) {
//使用TreeSet默認有序
Set<Integer> set=new TreeSet<Integer>();
//將陣列中的正整數全部拷貝到set集合中
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
set.add(nums[i]);
}
}
int size=set.size();
//如果沒有正整數，就回傳1
if(size==0){
return 1;
}
int arr[]=new int[size];
int j=0;
for(Integer x:set){
arr[j++]=x;
}
//如果最小正整數都大于1，那么缺失的第一個正數就是1
if(arr[0]>1){
return 1;
}
j=1; //測驗每個正整數是否在正整數陣列中出現
int k=0; //用來標記正整數陣列的下標
while(k<size){
//如果出現了， 兩者都加加
if(arr[k]==j){
k++;
j++;
}else{
//如果沒有出現，直接回傳該數即可
return j;
}
}
//如果一直都沒有找到，就回傳最大的值加1
return arr[size-1]+1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/263834.html
標籤：其他
上一篇：node+express 搭建商城專案（1-專案搭建）
下一篇：原生JS回傳頂部