6

我有一个家庭作业：

需要实现一个函数 (RotateRight) 来获取一个 INT 数组和一个数字：

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，则使用 x 大小的新 int[] tmpArray 将所有最后 x 项复制到它。然后使用 for 循环将所有其余的 int 向右移动。最后将 tmpArray 中的项目复制到原始数组的开头。

提前感谢您的任何建议或帮助

4

6 回答 6

5

您可以使用 Linq 语言的优点来返回 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#，但这里有两个 C++ 版本，都在原地，第一个 ( rotate) 通过利用旋转排列的循环结构执行尽可能少的元素移动，第二个 ( rotate_k) 只是2*n针对数组移动长度n。在这两个版本中，rotate right byk与 rotate left by 相同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 回答
0

C# 8 现在有索引和范围

右旋...

int[] r = t[1..].Concat(t[0..1]).ToArray();

向左旋转...

int[] r = t[^1..^0].Concat(t[..^1]).ToArray();

代替上面的“1”，也可以使用变量：int[] r = t[amt..].Concat(t[0..amt]).ToArray();

于 2020-01-09T01:21:20.093 回答