プログラマー面接100題の11:配列の循環シフト

2811 ワード

N個の要素を含む配列をKビット右シフトするアルゴリズムを設計し,時間複雑度O(N)を要求し,2つの付加変数のみを使用できるようにした.
問題に合わない解法は以下の通りです.
配列中の要素を1ビットずつ右にシフトし,K回サイクルできる簡単な方法を先に試験した.abcd1234--->4abcd123--->34abcd12--->234abcd1--->1234abcd.コードは次のとおりです.

RightShift(int *arr, int N, int K)
{
	while(K--)
	{
		int t = arr[N - 1];
		for(int i = N - 1 ; i > 0 ; i--)
		{
			arr[i] = arr[i - 1];
		}
		arr[0] = t;
	}
}

このアルゴリズムは配列のループ右シフトを実現できるが,アルゴリズムの複雑さはO(K*N)であり,問題の要求に合致せず,探索を継続する.
分析と解法
配列がabcd 1234であり,ループが4ビット右にシフトすると,我々が達成したい状態は1234 abcdである.Kは負の整数ではないとしてもよいが、Kが負の整数である場合、右シフトKビットは、左シフト(-K)ビットに相当し、左シフトと右シフトは本質的に同じである.
解法一
皆さんはこのような潜在的な仮説を持っているかもしれません.Kループ右シフトの特徴をよく見ると、各要素がNビット右シフトすると自分の位置に戻ることがわかります.したがって,K>Nの場合,右シフトK−N以降の配列配列は右シフトKビットの結果と同じである.さらに、右シフトKビット以降の場合は、右シフトK’=K%Nビット以降の場合と同様に、コードは以下のようになる一般的な法則が得られる.

RightShift(int *arr, int N, int K)
{
	K = K % N ;
	while(K--)
	{
		int t = arr[N - 1];
		for(int i = N - 1 ; i > 0 ; i--)
		{
			arr[i] = arr[i - 1];
		}
		arr[0] = t;
	}
}

ループ右シフトの特徴を考慮するとアルゴリズムの複雑さはO(N^2)に低下し,これはKとは無関係であり,問題の要求にまた一歩近づいたことがわかる.しかし、時間の複雑さはまだ低くありません.次に、ループの右シフト前後、配列間の関連を掘り起こし続けましょう.
解法二
文字列を2つのセグメントからなる、ビットXYと見なします.左回転は、文字列XYをYXにすることに相当します.まず、文字列に反転する操作を定義します.これは、文字列内の文字の前後順を反転することです.Xを反転させてXTと記す.明らかに(XT)T=Xがあります.
まずXとYの2つのセグメントをそれぞれ反転操作し,XTYPTを得ることができる.次にXTYTを反転操作して、(XTYT)T=(YT)T(XT)T=YXを得る.ちょうど私たちが期待していた結果です.
ここまで分析してから、元のテーマに戻ります.私たちがしなければならないのは文字列を2つのセグメントに分けて、第1のセグメントは前のm文字で、残りの文字は第2のセグメントに分けます.反転文字列の関数をもう1つ定義し、前の手順に従って3回反転すればいいです.時間の複雑さと空間の複雑さはいずれも要求に合っている.
元の配列シーケンスがabcd 1234であると仮定し、変換される配列シーケンスが1234 abcdであることが要求され、すなわち、ループが4ビット右にシフトした.比較すると、1234とabcdの2つのセグメントの順序が変わらないことがわかります.この2つのセグメントを2つの全体と見なすことができます.Kビットを右に移動するプロセスは、配列の2つの部分を交換し、変換のプロセスは次のステップで完了します.
1、逆配列abcd:abcd 1234--->dcba 1234;
2、逆順配列1234:dcba 1234--->dcba 4321;
3、すべての逆順:dcba 4321----->1234 abcd.
コードは次のとおりです.

Reverse(int *arr, int b, int e)      //    
{
	for( ; b < e; b++, e--)    //     、     
	{
		int temp = arr[e];
		arr[e] = arr[b];
		arr[b] = temp;
	}
}

RightShift(int *arr, int N, int K)
{
	K = K % N ;
	Reverse(arr, 0, N-K-1);     //  N-K    
	Reverse(arr, N-K, N-1);     //  K    
	Reverse(arr, 0, N-1);       //    
}

これにより,線形時間で右シフト動作を実現できるようになった.

SQLで実行中の合計を計算する4つの方法

[C++]白準16903号:数列とクエリー20