leetcode 41欠落の最初の正数(困難)
5708 ワード
leetcode 41が欠けている最初の正数要件は、並べ替えられていない整数配列を与え、そこに現れていない最小の正整数を見つけることである.时间の复雑さ:o(n)空间の复雑さ:o(1)多くの人はこの问题が简単だと思って、困难な区に置くべきではありませんて、実は大多数はすべて时间の复雑さと空间の复雑さを考虑していませんて、実は多くのアルゴリズムの问题はそっくりで、ただ时间の复雑さに対して要求をして実は前にselectモデルのビットマップの差が少ないと言ったのは概念で、このアルゴリズムはあまりにも巧みで、私が接触し始めたばかりの頃は本当に驚いた.例えば:3,1,4,5出力:2解法:あるアルゴリズムで3 1 4 5を1 5 3 4(すなわち1を第1の位置に、3を第3の位置に、4を第4の位置に、5を第2の位置に置くことができる)に並べることができれば、欠落した最初の正数が2であることを簡単に見つけることができます.次に、このアルゴリズムの実行過程3,1,4,5配列の長さは4の最初のステップi=0 a[i]=3であり、3を3番目の位置であるi=2の位置に置き、3と4,4,1,5を交換操作を実行すれば、iは自己増加しません.
第2ステップi=0 a[i]=4は、4番目の位置であるi=3の位置に4を置き、交換4と5 5,5,1,3,4は交換操作を実行すれば、iは自己増加しない
ステップ3 i=05>配列長4なので、5を5番目の位置に置くことができず、i++を交換することができません
第4ステップi=15,1,3,4 a[1]=1は、配列の第1の位置、すなわち下付き0の位置に1を置き、5と1は1,5,3,4の第5ステップi=1 a[1]=5であり、交換できない.i++第6ステップi=2 a[2]=3,3はすでに適切な位置にあり、交換できない.i++第7ステップi=3 a[3]=4,4はすでに適切な位置にあり、交換できない.i++
第2ステップi=0 a[i]=4は、4番目の位置であるi=3の位置に4を置き、交換4と5 5,5,1,3,4は交換操作を実行すれば、iは自己増加しない
ステップ3 i=05>配列長4なので、5を5番目の位置に置くことができず、i++を交換することができません
第4ステップi=15,1,3,4 a[1]=1は、配列の第1の位置、すなわち下付き0の位置に1を置き、5と1は1,5,3,4の第5ステップi=1 a[1]=5であり、交換できない.i++第6ステップi=2 a[2]=3,3はすでに適切な位置にあり、交換できない.i++第7ステップi=3 a[3]=4,4はすでに適切な位置にあり、交換できない.i++
public int firstMissingPositive(int[] nums) {
int len = nums.length;
if(null==nums||len==0)return 1;
//
for(int i=0;i<len;){
int cur = nums[i];
//
if(cur!=i+1&&cur<=len&&cur>0&&cur!=nums[cur-1]){
// i cur-1
nums[i] = nums[cur-1];
nums[cur-1] = cur;
}else{
++i;
}
}
//
for(int i=0;i<len;++i){
if(i+1!=nums[i]){
return i+1;
}
}
// 1 2 3 4
return len+1;
}