M位置のサークルシフトアレイの最速のアルゴリズムは何ですか？
たとえば、[3 4 5 2 3 1 4]シフトM=2の位置は。である必要があります[1 4 3 4 5 2 3]。
どうもありがとう。
33710 次
25 に答える
56
(配列が指定されているため) O(n) 時間で余分なメモリ使用量が必要ない場合は、Jon Bentley の本「Programming Pearls 2nd Edition」のアルゴリズムを使用してください。すべての要素を 2 回交換します。リンクされたリストを使用するほど高速ではありませんが、メモリの使用量が少なく、概念的に単純です。
shiftArray( theArray, M ):
size = len( theArray )
assert( size > M )
reverseArray( theArray, 0, size - 1 )
reverseArray( theArray, 0, M - 1 )
reverseArray( theArray, M, size - 1 )
reverseArray( anArray, startIndex, endIndex ) は、startIndex から endIndex までの要素の順序を逆にします。
于 2009-05-18T05:46:56.350 に答える
23
それは単なる表現の問題です。現在のインデックスを整数変数として保持し、配列をトラバースするときは、モジュロ演算子を使用して、いつラップアラウンドするかを確認します。シフトとは、現在のインデックスの値を変更するだけで、配列のサイズにラップします。もちろんこれはO（1）です。
例えば：
int index = 0;
Array a = new Array[SIZE];
get_next_element() {
index = (index + 1) % SIZE;
return a[index];
}
shift(int how_many) {
index = (index+how_many) % SIZE;
}
于 2009-05-18T05:07:59.163 に答える
8
ポインタを使って設定すれば、ほとんど時間がかかりません。各要素は次の要素を指し、「最後」（最後はありません。結局のところ、円形であると言いました）は最初の要素を指します。「開始」（最初の要素）への1つのポインター、そしておそらく長さ、そしてあなたはあなたの配列を持っています。ここで、シフトを行うには、開始ポインターを円に沿って歩くだけです。
良いアルゴリズムを求めれば、賢明なアイデアが得られます。最速を求めると、奇妙なアイデアが浮かびます！
于 2009-05-18T04:58:48.600 に答える
4
def shift(nelements, k):
result = []
length = len(nelements)
start = (length - k) % length
for i in range(length):
result.append(nelements[(start + i) % length])
return result
このコードは、負のシフト k でもうまく機能します
于 2012-10-15T01:50:54.410 に答える
3
CarrayShiftRight関数。shiftが負の場合、関数は配列を左にシフトします。メモリ使用量を減らすために最適化されています。実行時間はO（n）です。
void arrayShiftRight(int array[], int size, int shift) {
int len;
//cut extra shift
shift %= size;
//if shift is less then 0 - redirect shifting left
if ( shift < 0 ) {
shift += size;
}
len = size - shift;
//choosing the algorithm which needs less memory
if ( shift < len ) {
//creating temporary array
int tmpArray[shift];
//filling tmp array
for ( int i = 0, j = len; i < shift; i++, j++ ) {
tmpArray[i] = array[j];
}
//shifting array
for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) {
array[i] = array[j];
}
//inserting lost values from tmp array
for ( int i = 0; i < shift; i++ ) {
array[i] = tmpArray[i];
}
} else {
//creating temporary array
int tmpArray[len];
//filling tmp array
for ( int i = 0; i < len; i++ ) {
tmpArray[i] = array[i];
}
//shifting array
for ( int i = 0, j = len; j < size; i++, j++ ) {
array[i] = array[j];
}
//inserting lost values from tmp array
for ( int i = shift, j = 0; i < size; i++, j++ ) {
array[i] = tmpArray[j];
}
}
}
于 2012-07-16T15:33:35.943 に答える
2
これは、配列を循環的にシフトするために機能するはずです。forloops の後の配列に存在する出力値: {8,7,1,2,3,5,6,8,7}
class Program
{
static void Main(string[] args)
{
int[] array = { 1, 2, 3, 5, 6, 7, 8 };
int index = 2;
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
for (int i = 0; i < array.Length - index; i++)
{
array[index + i] = tempArray[i];
}
for (int i = 0; i < index; i++)
{
array[i] = tempArray[array.Length -1 - i];
}
}
}
于 2013-02-23T14:31:00.627 に答える
1
static int [] shift(int arr[], int index, int k, int rem)
{
if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)
{
return arr;
}
int temp = arr[index];
arr = shift(arr, (index+k) % arr.length, k, rem - 1);
arr[(index+k) % arr.length] = temp;
return arr;
}
于 2011-03-13T20:50:53.060 に答える
1
使用するデータ構造に応じて、O（1）で実行できます。最速の方法は、リンクリストの形式で配列を保持し、配列内の「インデックス」からエントリへの「ポインタ」に変換できるハッシュテーブルを用意することだと思います。このようにして、O（1）で関連するヘッドとテールを見つけ、O（1）で再接続を実行できます（O（1）で切り替えた後にハッシュテーブルを更新します）。もちろん、これは非常に「厄介な」解決策になりますが、シフトの速度だけに関心がある場合は、それで十分です（配列への挿入とルックアップが長くなりますが、それでもO（ 1））
純粋な配列のデータがある場合、O（n）を回避することはできないと思います。
コーディングに関しては、使用している言語によって異なります。
たとえばPythonでは、それを「スライス」することができます（nがシフトサイズであると仮定します）。
result = original[-n:]+original[:-n]
（ハッシュルックアップは理論的にはO（1）ではないことを知っていますが、ここでは実用的であり、理論的ではありません。少なくともそう願っています...）
于 2009-05-18T05:07:15.903 に答える
1
理論的には、最速のものは次のようなループです。
if (begin != middle && middle != end)
{
for (i = middle; ; )
{
swap(arr[begin++], arr[i++]);
if (begin == middle && i == end) { break; }
if (begin == middle) { middle = i; }
else if (i == end) { i = middle; }
}
}
実際には、プロファイルを作成して確認する必要があります。
于 2013-11-04T05:06:03.523 に答える
1
このメソッドはこの作業を行います:
public static int[] solution1(int[] A, int K) {
int temp[] = new int[A.length];
int count = 0;
int orignalItration = (K < A.length) ? K :(K%A.length);
for (int i = orignalItration; i < A.length; i++) {
temp[i] = A[count++];
}
for (int i = 0; i < orignalItration; i++) {
temp[i] = A[count++];
}
return temp;
}
于 2016-12-02T08:54:59.670 に答える
1
これは別のものです（C ++）：
void shift_vec(vector<int>& v, size_t a)
{
size_t max_s = v.size() / a;
for( size_t s = 1; s < max_s; ++s )
for( size_t i = 0; i < a; ++i )
swap( v[i], v[s*a+i] );
for( size_t i = 0; i < a; ++i )
swap( v[i], v[(max_s*a+i) % v.size()] );
}
もちろん、有名なリバース 3 回のソリューションほどエレガントではありませんが、マシンによっては同様に高速になる場合があります。
于 2014-05-16T12:48:22.330 に答える
1
circleArrayいくつかのエラーがあり、すべての場合に機能していません!
ループは継続しなければなりwhile i1 < i2ませんi1 < last - 1。
void Shift(int* _array, int _size, int _moves)
{
_moves = _size - _moves;
int i2 = _moves;
int i1 = -1;
while(++i1 < i2)
{
int tmp = _array[i2];
_array[i2] = _array[i1];
_array[i1] = tmp;
if(++i2 == _size) i2 = _moves;
}
}
于 2009-10-08T10:57:54.467 に答える
1
Java 実装に興味がある場合は、これを参照してください。
于 2011-07-05T06:18:07.207 に答える
1
配列を左にシフトするための Swift 4 バージョン。
func rotLeft(a: [Int], d: Int) -> [Int] {
var result = a
func reverse(start: Int, end: Int) {
var start = start
var end = end
while start < end {
result.swapAt(start, end)
start += 1
end -= 1
}
}
let lenght = a.count
reverse(start: 0, end: lenght - 1)
reverse(start: lenght - d, end: lenght - 1)
reverse(start: 0, end: lenght - d - 1)
return result
}
たとえば、入力配列がa = [1, 2, 3, 4, 5]で、左シフト オフセットがd = 4の場合、結果は次のようになります。[5, 1, 2, 3, 4]
于 2018-08-13T18:59:02.430 に答える
0
配列に 2 つのインデックスを保持します。1 つのインデックスは、配列の先頭から配列の末尾までです。別のインデックスは、最後から M 番目の位置から開始し、最後の M 要素を何度でもループします。常に O(n) を取ります。余分なスペースは必要ありません。
circleArray(Elements,M){
int size=size-of(Elements);
//first index
int i1=0;
assert(size>M)
//second index starting from mth position from the last
int i2=size-M;
//until first index reaches the end
while(i1<size-1){
//swap the elements of the array pointed by both indexes
swap(i1,i2,Elements);
//increment first pointer by 1
i1++;
//increment second pointer. if it goes out of array, come back to
//mth position from the last
if(++i2==size) i2=size-M;
}
}
于 2009-08-03T19:16:25.017 に答える