3

shift(int* arr, int k)配列を整数kだけ循環的にシフトする関数を作成するにはどうすればよいですか？ヒープから「malloc」メモリを言うことはできません。

たとえば、擬似コードを使用すると、をshift([1, 2, 3, 4], 2)返し[3, 4, 1, 2]、をshift([3, 1, 5, 5], 103)返します[1, 5, 5, 3]。このJavaプログラムに示されているように、モジュラスを使用してこの効果を達成しようとしました。このプログラムでは、基本的に配列の半分を反復処理し、値を交換します。

public static int* shift(int* arr, int k) {
  int half_array_len = arr.length / 2;
  for (int i = 0; i < half_array_len; ++i) {
    // Swap!
    int newIndex = (i + k) % arr.length;
    int temp = arr[i];
    arr[i] = arr[newIndex];
    arr[newIndex] = arr[i];
  }
  return arr;
}

ただし、この関数は偶数の長さの配列でのみ機能すると思います。

shift任意の長さの配列にどのように実装できますか？回答は、任意の言語（Java、C ++、Ook Ook！など）にすることができます。

4

2 に答える 2

10

（これまでに何度か質問されています。）基本的に、この問題を解決するための3つの古典的なインプレースアルゴリズムは、Bentleyの「ProgrammingPearls」（ジャグリング、リバーサル、ブロックスワップアルゴリズム）で説明および分析されています。これらのスライドは、それらを十分に詳細に説明しています

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

最も単純なアルゴリズムは反転アルゴリズムです。アレイ全体を反転してから、各[n--k]および[k]ブロックを個別に反転します。終わり。（どちらの端から[k]ブロックがカウントされるかは、シフトの方向によって異なります。）

もちろん、最初の値を正規化することは理にかなっていますk。つまり、が。未満であるk = k % nことを確認するために実行します。kn

PS C ++では、答えはを使用するstd::rotateことです。これは、まさにあなたが望むことを実行します。しかし、これがあなたが求める答えではないかと思います。ただし、のいくつかの実装を確認することをお勧めしますstd::rotate（通常、反転アルゴリズムを使用していることを発見した場合のみ:)

于 2012-12-06T04:10:18.770 に答える
1

この機能を実行するには、一定量の追加スペースしか使用できないということだと思います。O(n*(k mod n))これは、次のアルゴリズム（Python）を使用して、1つの一時的な時間で実行できます。

def shift_one(array):
    temp = array[-1] #put last element of array in a temp
    for i in range(len(array)-1)[::-1]:
        array[i+1] = array[i] #put each element in the next slot
    array[0] = temp #then put the temp at the beginning
    return array

def shift(array, k):
    for i in range(k%len(array)):
        array = shift_one(array)
    return array

実際に一定の追加スペースに制約されていない場合は、次のアルゴリズム（ほぼ同じこと）を使用して、時間k内に追加スペースでそれを行うことができます。O(n)

def shift(array, k):
    k = k % len(array) #shifting by len(array) does nothing
    temp = array[-k:] #copy out the last k elements
    for i in range(len(array)-k)[::-1]:
        array[i+k] = array[i]
    array[:k] = temp
    return array

また、Pythonのように、配列よりもはるかに多くのことを実行できるリストがある場合は、非常に簡単な解決策があります。

def shift(array, k):
    #take the last k elements and put them at the front
     return array[-k:]+array[:-k]
于 2012-12-06T04:04:01.757 に答える