剣はofferの第3題を指します——配列の中で繰り返した数字-テーマ1

2782 ワード

前言
今度は何も言わずにやってしまった
テーマ
長さnの配列のすべての数字は0~n-1の範囲にある.配列の中にはいくつかの数字が重複していますが、いくつかの数字が重複しているのか、数字ごとに何回重複しているのか分かりません.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力と、対応する出力は重複する数字2または3となる.
二構想
著者はこのような問題を解決するには2つの大きな考え方があると述べた.

ソート.序列が終わると、何の魑魅魍魉も見られる.

ハッシュ表.1つの数字をスキャンするたびに対応するハッシュテーブルに格納され、テーブルにすでに数字があることに気づいたら、その数字が重複していることを示します.時間的複雑度はO(n)O(n)O(n),空間的複雑度はO(n)O(n)O(n)

であった.
2.1基本思想
この問題を解決するには,順序付けが基本的な考え方であるが,一般的な順序付けであればもう1つの対比が複雑すぎるのではないか,ここでは配列の1つの法則を利用して,順序付けの過程で重複する項目を探すことができる.
1 D配列はメモリに連続した空間を占めるため、対応する要素を下付きスケールに基づいて位置決めできます.
配列中の数字はいずれも0~n−1の範囲内であることに気づいた.この配列に重複する数字がない場合、配列がソートされると、数字iがiとして下に表示されます.配列に重複する数字があるため、一部の数字は自分の下付きの位置に加えて、他の下付きの位置を占める可能性があり、一部の位置には数字がない可能性があります.

最初から最後まで配列全体a[]を掃く.

下のiの数字をスキャンした場合、この数字a[i]がiに等しいか否かを判断する.a[i]=iであれば、1を回して次の要素をスキャンし続けます.a[i] != iであれば、3を回します.

は現在a[i] != iが知られており、a[ a[i] ]とa[i]が等しいかどうかを判断し、等しい場合は、この数字が重複していることを説明し、直接値を付けて出力する.もしa[a[i]!=a[i]， a[ a[i] ]の内容とa[i]の内容が入れ替わる.

はこのように循環し、最後の重複数を得る.

上のアルゴリズムをどのように理解するかは、配列の数を観察する法則から得られます.
0
1
2
3
4
5
6
2
3
1
0
2
5
3
1
3
2
0
2
5
3
3
1
2
0
2
5
3
0
1
2
3
2
5
3
第1の行為の下で、第2の行為の配列の中の各要素、第3から最後の行は全体のプログラムの実行の過程で、1回歩いて、アルゴリズムの精髄を理解することができます.
いいですね~!
2.2実装

bool duplicate( int numbers[], int length, int * duplication )
{
	//     ： 1.      、    0； 2.        0~n-1
	if ( (numbers == nullptr) || (length <= 0) )
	{
		return false;
	}
	for (int i = 0; i < length; i++)
	{
		if (  (numbers[i] < 0) || (numbers[i] > length-1) )
			return false;
	}
	
	//      
	for (i = 0; i < length; i++) //          
	{
		while (numbers[i] != i) //            
		{//    
			if ( numbers[i] == numbers[ numbers[i] ] ) //          
			{
				*duplication = numbers[i];
				return true;
			}
			//         ，     numbers[i]      
			int temp = numbers[i];
			numbers[i] = numbers[temp];
			numbers[temp] = temp;
		}// end while
	}// end for

	return false; //    
}

2.3性能分析

時間複雑度:O(n)O(n)O(n)はforとwhileが見られ、実際には各元素が2回まで位置を交換するので、時間複雑度はO(n)O(n)O(n)

である.

空間複雑度:O(1)O(1)O(1)

2.4テストセット

長nの配列には、1つ以上の繰り返し数

が含まれる.

配列には重複数

は含まれていない.

無効な入力(空のポインタ;配列要素は0-n-1の間にない数字が存在する)

三収穫

配列の最も顕著な特徴は、連続アドレスのセットの記憶空間である.私たちはそれを利用していろいろなことをすることができます.ここでは、その下付き文字と要素の対応関係

を利用しています.

はできませんか?データを持って法則を探しましょう.

参考文献
[1]何海濤著.剣指OFFER名企面接官精講典型プログラミング問題第2版[M].北京:電子工業出版社.2017.

Windows 2012インストールoracleレポートINS-13001環境が最低要件を満たしていない

ibatis操作戻り値