筆記試験問題54.LeetCode OJ (41)

この問題は無秩序配列の中の最初の不連続な正の整数を探し出し,時間複雑度はO(n)を超えない.まず解析すると,配列は無秩序であり,最初の不連続な数字を見つける必要があるが,並べ替えアルゴリズムは一般にO(n)の時間的複雑さに達することが困難である.この时、私达は1种の方法を理解しなければなりません:空间は时间の方法を交换して、私はまずビットマップつまりbitmap(STLの中でbitsetを交际します)を考えて、ビットマップは空间を节约することができて、その上数字が现れるかどうかを判断することができて、本当に理想的なデータ构造です.そこで私は関数でbitsetを使いました.

const int N = nums.size();
bitset<N> BitSet;

         
私はこの文がクラスの中で通用しないことを発見して、C++の中でconst修飾の変数は常性を持っていて、しかし関数の体内で使う時通用しないで、本当にもったいないので、自分で1つのbitmapを実現してまた面倒に見えて、そこで私はbitmapを使うことを放棄することにしました(これはbitmapがだめではありません).テーマが私たちに与えられたvectorである以上、私はvectorをbitmapとして使います.空間的には低効率ですが(今になってvectorのようなvectorが空間を節約できることを思い出しました)、大きな影響はないでしょう.そこで私は使いました.

size_t len = nums.size();
vector<int> v;
v.resize(len);

注意深い人はきっと言います.もしnumsの中の数字が大きいとしたら、あなたの配列の下付き文字はそんなに大きくなりません.このように値をつけるとプログラムが崩壊します.実は、私たちはやる必要がないことがあります.私の考えはこうです.numsの数グループの中の数字は[0,len]の範囲内で、私たちは新しいvectorを1にします.
超えた私たちが直接スキップしたら、スキップは思考が厳密ではないのではないでしょうか.
私が言いたいのは、私のvectorの大きさは配列numsの大きさと同じ大きさで、numsがすべての要素が正で秩序正しくても、私たちはすべて詰めることができます.無秩序であれば、最初の切断された場所は必ず真ん中にあり、配列の範囲を絶対に超えません.だから、上記の状況は存在しません.コードを見てください.

class Solution {
public:
	int firstMissingPositive(vector<int>& nums)
	{
	    //              ，    bitset     ，       ，      nums.size()+1      ，           ，              ，          
		const size_t len = nums.size();
		vector<int> tmp;
		tmp.resize(len + 1);
		for (size_t i = 0; i < len; ++i)
		{
			if (nums[i] > 0 && nums[i] <= len)
			{
				tmp[nums[i]] = 1;
			}
		}

		for (size_t i = 1; i < len + 1; ++i)
		{
			if (tmp[i] == 0)
			{
				return i;
			}
		}

		return len + 1;
	}
};

結果: