分散学的アルゴリズムのうち、配列中の繰り返しの数を見つける---総括編

4322 ワード

配列内の繰り返しの数を探します.
前の順序

最近ずっと見ていますJULYvのコラムでは、アルゴリズムに関する多くの知識を学び、大きな啓発を受けました.アルゴリズムが好きな友達は彼のブログを見てからもそう思うと思います.この前、面接に参加しました.彼のコラムから学んだアルゴリズムは私に多くの助けを与えました.これは面接の時に楽になりました.彼のブログは引き続き注目して勉強します.
じゃ、本題に戻ります.配列中の重複数を見つけるという問題については、ネット上ですでに多くの文章が述べられている.しかし、皆さんはこの問題についてあまり全面的に考えていないと思います.
  問題の説明:配列A[N]をあげます.この配列にはN個の自然数が保存されています.要求は配列の中で重複しているその数を探し出すことです.
  この問題については、二つの状況に分けて検討できると思います.
ケース1:このN個の大きさは1−−N−1の間です.A[5]:2、1、3、1、4のように.
ケース2:このN個の数の大きさは任意で、このN個の数は1-N-1の区間にあるかもしれません.A[7]:1、3、5、7、9、9、11.
  実は情況の1つは情況の2つの特例です.しかし情況の1に適する解法は情況の2に適合するとは限らなくて、しかし情況の2に適するのはきっと情況の1に適します.
第一の場合、つまり、このN個の大きさは1−−N−1の間で実現できる多くの方法がある.ここでは、このような状況にしか当てはまらないと言っていますが、情況二の解法には向かないです.
まず最初に思いついたのは数学を利用する方法で、私はそれを求めて差法をします.この方法の考えは、2つの変数TempSum 1、TempSum 2を宣言し、簡単なforサイクルを利用して、TempSum 1=1+2+N、TempSum 2=A[0]+A[1]+……[N-1]を利用して、N-(TempSum 1-TempSum 2)を通じてこの重複した数を得ることである.実現コードは以下の通りです.

int RepeatNum(int *Array, int N)
{
	int i;
	int TempSum1 = 0, TempSum2 = 0;
	for(i = 0;i < N;i++)
	{
		TempSum1 = i + 1;
		TempSum2+ = Array[i];
	}
	return N-(TempSum1 - TempSum2) ;
}

解法二:
ネットではこの解法をマーク配列法と呼びます.この解法の核心思想は、配列長N-1の文字列配列Help[N-1]を申請し、配列の各項目を最初に'0'、そして最初から行列A[N]を遍歴し、A[i]の値を取って、
Help配列上の対応する位置、すなわちHelp[A[i]='1'は、この位置がすでに'1'にセットされているなら、この数はその繰り返しの数である.この方法の実現コードは以下の通りである.

int RepeatNum(int *Array, int N)
{
	int i;
	char Help[N-1];
	for(i = 0;i < N-1;i++)
	{
		Help[i] = '0';
	}
	for(i = 0;i < N;i++)
	{
		if(Help[A[i]-1] == '1')
			return A[i];
		else
			Help[A[i-1]] = '1';
	}
}

解法三:
固定オフセットマーク法
.この方法は私がネットで探したものです.この解法の核心思想はA[N]自身の中の値と下の表記の関係を利用してマークを付けて、処理が終わったらマークを明確にすればいいです.配列A[N]に対して最大の数はN-1であり、A[i]=Mがどこかに現れたら、A[M]を一度Nを加えてマークし、どこかにA[i]= K再成立時には、A[K]を見て、Kがすでに存在していることが分かります.A[i]プログラムで一番大きいのはN-1+N=2*N-1で、範囲外ではないですか?大丈夫です.私たちはそれを制限条件として利用できます.実現コードは以下の通りです.

int RepeatNum(int *Array,int N)
{
	int temp=0;
	
	for(int i=0; i<N; i++)
	{
		if(Array[i] >= N)
			temp = Array[i]-N; //      ，         
		else 
			temp = Array[i];

		if(Array[temp] < N) 
		{
			Array[temp]+ = N; //    
		}
		else 
		{    
			return temp; //   ；
		}
	}
		return -1;//   
}

はい、状況一に対する解法はとりあえずこれです.もっといい解法があれば、教えてください.次に、状況二に対応する関連解について検討します.
ケース2、すなわち、このN個の数の大きさは任意である.ここでは三つの解法を示します.前の二つの解法は基礎的です.
解法の1:私達は2つのforで循環して解決することができます.とても簡単で、これは最も簡単な並べ替えのアルゴリズムを学ぶようです.しかし、アルゴリズムの効率はあまりにも低いです.コア思想は言わないで、直接コードを見てください.

int RepeatNum(int *Array,int N)
{
	int i, j;
	
	for(i = 0;i < N - 1;i++)
	{
		for(j = i + 1;j <= N - 1; j++)
		{
			if(Array[i] == Array[j])
			{
				return Array[j];
			}
		}
	}
}

解法二:この配列の要素は無秩序である可能性が高いので、この問題を入手すると、解法一は通常先述します.しかし、解法一の効率はよくないです.(時間の複雑さはO(N＊N)です.どうやって上げますか?はい、解法二を見てみます.解法二の思想はとても簡単で、配列に対して一回の順序付けをして、配列を秩序化させます.つまり小さい時から大きい時まで、あるいは大きい時から小さい時までです.並べ替えをすると、私たちが選択できる優れた並べ替えアルゴリズムがたくさんあります.例えば、高速並べ替え、積み上げ、並べ替えなど、これらの並べ替えアルゴリズムの時間の複雑さはO(N＊LgN)です.どれを選んでもいいです.順序付けが完了したら、配列A[N]が秩序配列になり、この順序配列からその繰り返しの数を見つければ問題は解決され、一回の循環をすれば解決できます.具体的な方法は:最初からこの順序配列を遍歴して、現在の数と後の数が等しい時は私達が探しているその繰り返しの数です.同じではない時はi＋＋だけで、グループ数を比較して、その繰り返しの数を探し出します.この解法に対して、時間の複雑さは
O(N＊LgN＋N).実現コードは以下の通りです.

int RepeatNum(int *OrderArray,int N)
{
    int i;
    for(i = 0;i < N;i++)
    {
        if(OrderArray[i] == OrderArray[i+1])
            return OrderArray[i];
    }
}

上記の二つの解法は簡単にできるはずです.もっといい方法がありますか?もちろんあります.次は第三の方法を紹介します.
この問題はハッシュアルゴリズムで解決できると思います.ハッシュアルゴリズムを利用して、キーと実値との間の対応関係を確立することができる.各本物の値はキーパッドの値しかないですが、各キーの値は複数の本物の値に対応できます.このようにして、配列の中で私たちが欲しい数を素早く見つけられます.そして、ハッシュアルゴリズムを利用して、この問題に対して時間の複雑さを最適化することができます.ハッシュアルゴリズムとその原理について、インターネットでいくつかの資料を探して共有しました.
ハッシュアルゴリズムの原理:http://wenwen.soso.com/z/q181569235.htm
        ハッシュアルゴリズム:http://baike.soso.com/ShowLemma.e?sp=l7892037&ch=w.search.baike.unelite
        有名なハッシュアルゴリズム:http://blog.csdn.net/longronglin/article/details/1782678
        豪雪のハッシュアルゴリズム:http://opaque.blogbus.com/logs/30017835.html
OKです.以上は配列の中で繰り返しを求めるいくつかの解法です.でも、この問題に対する解決法は上記だけではないと信じています.もっといい解決法があると思います.

デザインモード---ポリシーモード(組み合わせ)

復号アルゴリズムRSA、AES、DES、MD 5の使用例と違い