0

数値の配列を受け取り、数値をシフトし、シフトされた配列を返すメソッドを作成しました。

次のように：

private static int[] ShiftArray(int[] arr, int shift)
{
    shift = shift % arr.Length; 
    int[] tmpArr = new int[shift];
    for (int i = 0; i < tmpArr.Length; i++)
    {
        tmpArr[i] = arr[arr.Length - 1 - i];
    }
    for (int i = arr.Length - 1; i >= shift; i--)
    {
        int index = Math.Abs(i - shift);
        if (index >= 0)
        {
            arr[i] = arr[index];
        }
    }
     for (int i = 0; i < tmpArr.Length; i++)
        {
            arr[i] = tmpArr[tmpArr.Length - 1 - i];
        }
    return arr;
}

メモリを消費しないようにメソッドを改善したい。それを改善する方法と、このメソッドに割り当てられているメモリの量を確認する方法について教えていただければ幸いです。

編集

例 1:

Input: int[]{1,2,3,4,5,6}, shift:2
Output: int[]{5,6,1,2,3,4}

例 2:

Input: int[]{1,2,3,4,5,6}, shift:15
Output: int[]{4,5,6,1,2,3}
4

1 に答える 1

0

次のように、配列のインプレース右回転を実行できます。

private static int[] ShiftArray(int[] arr, int shift)
{
    shift = arr.Length - (shift % arr.Length);
    Array.Reverse(arr, 0, shift);
    Array.Reverse(arr, shift, arr.Length-shift);
    Array.Reverse(arr);
    return arr;
}

ただし、これは仕様が要求することを完全には行いません。しかし、それは右回転を行っています。

あなたの仕様から：

編集: 例 1: 入力: int[]{1,2,3,4,5,6}, shift:2 出力: int[]{5,6,1,2,3,4}

例 2: 入力: int[]{1,2,3,4,5,6}, shift:15 出力: int[]{6,5,4,1,2,3}

私のコードは、例 1 と同じものを出力しますが、例 2 では次のように出力します。

5、6、1、2、3、4

これは右シフトに適しています (常に要素を同じ順序のままにします)。

しかし、仕様にはいくつかの要素が異なる順序で含まれています。これは、実際には右シフトではなく、より複雑なものであることを意味します。(または、仕様にエラーがあります!)

(Jon Bentley による本 Programming Pearls には、配列を回転させるためのこのようなアルゴリズムがあります。)

于 2013-05-09T10:41:25.127 に答える