6

宿題があります：

INT と数値の配列を取得する関数 (RotateRight) を実装する必要があります。

int[] res = RotateRight(new int[] { 1, 2, 3, 4, 5, 6 }, 2);
//so then res will be {5,6,1,2,3,4}

与えられた数に従ってすべてのアイテムを右に回転させた後、配列を返します。この場合は 2.

そして、メモリ空間の観点からこれを効率的に行う必要があります。

私の最高のアイデアは次のとおりです。

与えられた数が x の場合、新しい int[] tmpArray を x のサイズで使用して、最後の x 項目をすべてそれにコピーします。次に、 for ループを使用して残りのすべての int を右にシフトします。最後に、tmpArray 内の項目を元の配列の先頭にコピーします。

アドバイスやヘルプを事前にありがとう

4

6 に答える 6

5

Linq langage の美しさを利用して、配列サイズを扱わずに IEnumerable を返すことができます。

/// <summary>
/// Get c = a mod (b) with c in [0, b[ like the mathematical definition
/// </summary>
public static int MathMod(int a, int b)
{
    int c = ((a % b) + b) % b;
    return c;
}
public static IEnumerable<T> ShiftRight<T>(IList<T> values, int shift)
{
    for (int index = 0; index < values.Count; index++)
    {
        yield return values[MathMod(index - shift, values.Count)];
    }
}

使用法 ：

[TestMethod]
public void TestMethod1()
{
    var res = ShiftRight(new [] { 1, 2, 3, 4, 5, 6 }, 2).ToArray();
    Assert.IsTrue(res.SequenceEqual(new[] { 5, 6, 1, 2, 3, 4 }));
}
于 2013-11-12T16:05:04.013 に答える
1

可能な限り多くのメモリを使用しても意味がありません。おそらくメモリをできるだけ少なくするという意味ですか? その場合、XOR を使用して配列内の各項目を交換する必要があります。

var a = 2096;
var b = 842390;

a ^= b;
b ^= a;
a ^= b;

これらの番号を交換します。

編集

すべてを適切に実行するコード:

    public static void RotateRight(int[] input, int right)
    {
        for (var i = 0; i < right; i += 1)
        {
            RotateRightOne(input);
        }
    }

    public static void RotateRightOne(int[] input)
    {
        var last = input.Length - 1;
        for (var i = 0; i < last; i += 1)
        {
            input[i] ^= input[last];
            input[last] ^= input[i];
            input[i] ^= input[last];
        }
    }

使用法：

    var arr = new[] {1, 2, 3, 4, 5, 6};
    RotateRight(arr, 2);

Servyが指摘しているように、これは整数専用です

于 2013-11-12T16:08:05.103 に答える
0

C# はわかりませんが、ここに 2 つの C++ バージョンがあります。両方とも配置されています。最初の ( rotate) は、回転順列の循環構造を利用して可能な限り少ない数の要素の移動を行います。2 番目の ( rotate_k)2*nは、配列の移動のみを行います。長さn。どちらのバージョンでも、右k回転は左回転と同じであることが使用されn - k % nているため、実際には同等の左回転を行います。

#include <iostream>
#include <vector>
#include <algorithm>

void
rotate (size_t k, std::vector<int> &a) {
    size_t n = a.size();
    k = n - k % n;

    size_t m = n;

    size_t i = 0;
    while (m > 0) {
        int t = a[i];
        size_t j = i;
        while (i != (j + k) % n) {
            a[j] = a[(j + k) % n];
            j = (j + k) % n;
            --m;
        }
        a[j] = t;
        --m;
        ++i;
    }
}

void
rotate_k (size_t k, std::vector<int> &a) {
    size_t n = a.size();

    k = n - k % n;

    std::reverse (a.begin(), a.end());
    std::reverse (a.begin(), a.begin() + n - k);
    std::reverse (a.begin() + n - k, a.end());
}

int
main () {
    std::vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    rotate (12, a);

    for (auto i : a)
        std::cout << i << " ";

    std::cout << std::endl;
}
于 2013-11-13T23:43:26.093 に答える
0

実際に k 回回転させるのではなく、k 回回転させた後に各要素の最終的なインデックスを把握する必要があります。これは私のために働いた：

for(int i=0;i<a.Length;i++){
        rotated[(k+i)%(a.Length)]=a[i];
    }
于 2017-01-27T19:09:58.820 に答える
0

配列 A を右に K ステップ回転させる簡単なサンプルを次に示します。

    var splitPoint=A.Length-(K%A.Length);

    var result=new int[A.Length];
    int idx=0;
    for(var pos=0;pos<A.Length;pos++)
    {
      if(pos<A.Length-splitPoint)
      {
        result[pos]=A[splitPoint+pos];    
      }
      else
      {
        result[pos]=A[idx];
        idx++;
      }
    }

    return result;
于 2018-05-17T19:03:26.810 に答える