5

晚安，人们！

我正在尝试解决一个相当简单的问题，但是.. 好吧，似乎我做不到。:)

这个想法是我有一个包含 n 个元素的 FIFO 列表（FIFO 队列），并且它被赋予了一个值 k (k < n)。我的小程序必须用 k 个元素将元素向左移动。（例如对于 n=4, k=3, a[]=(1, 2, 3, 4)，结果是 4 1 2 3）。

但好吧，我离那还很远。

这是我到目前为止所写的：

#include <iostream>
using namespace std;

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=0; i<=n-1; i++) t[i]=a[i];
        for (i=0; i<=k-1; i++) a[i]=a[i+k-1];
        for (i=k; i<=n-1; i++) a[i]=t[i+1];
}

int main () {
        int a[100];
        unsigned k, n, i;
        cout<<"n; k= "; cin>>n>>k;
        for (i=0; i<=n-1; i++) cin>>a[i];
        move (a, n, k);
        for (i=0; i<=n-1; i++) cout<<a[i]<<" ";
}

任何帮助将不胜感激。先感谢您。

4

6 回答 6

2

我不确定我是否完全理解了你的问题。但看起来您实际上想要旋转数组的内容。

将数组内容向左旋转 k 次。您可以执行以下操作：

  • 反转前 K 个元素。
  • 反转剩余的 NK 元素。
  • 反转整个数组。

例子：

N = 5，K = 3，数组 = [1 2 3 4 5]

  • 第 1 步：反转前 3 个元素：[3 2 1 4 5]
  • 第2步：反转剩余的2个元素：[3 2 1 5 4]
  • 第 3 步：反转整个数组：[4 5 1 2 3]

C++ 函数做同样的事情：

void move (int a[100], int n, int k) {
        int t[100];
        int i,j;
        for (i=k-1,j=0; i>=0; i--,j++) t[j]=a[i];
        for (i=n-1; i>=k; i--,j++) t[j]=a[i];
        for (i=n-1,j=0; i>=0; i--,j++) a[j]=t[i];
}

在恒定空间中执行此操作的更好方法是就地进行反转：

void arr_rev(int a[100], int start, int end) {
        int temp;

        for(;start<end;start++,end--) {
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
        }
}

void move2 (int a[100], int n, int k) {
        arr_rev(a,0,k-1);
        arr_rev(a,k,n-1);
        arr_rev(a,0,n-1);
}
于 2010-02-03T18:23:15.727 回答
1

看起来你想要左旋转？这应该不是很困难。只需将第一个k元素出列，将剩余n-k元素向左移动（可能通过将它们放在临时数组的开头），然后k按顺序在末尾添加第一个元素。

以这种方式修改您的代码可能如下所示：

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=k; i<=n-1; i++) t[i-k]=a[i];
        for (int x=0; x<=k-1; x++) t[i++-k]=a[x];
}

而且由于这仍然很难看，您可以重写它以使逻辑更清晰，但我将把它留作练习。

这也假设您不允许使用 STL 数据结构；如果不是这样，请参阅 Jerry Coffin 的回答。

于 2010-02-03T18:02:59.960 回答
1

由于您已将其标记为 C++，因此我假设您正在使用它。在这种情况下，您几乎可以肯定使用 anstd::deque而不是数组来存储数据。另外，一个队列通常有一个“前”和一个“后”，所以“左”并没有太大的意义。

假设（只是为了论证）你想要的是从队列的后面取出 k 个元素并将它们移动到前面，你可以这样做：

typedef std::deque<your_type> data;

void push_to_front(data &d, int k) { 
    if (k > d.size())
        return;
    for (int i=0; i<k; i++) {
        data::value_type v = d.pop_back();
        d.erase(d.back());
        d.push_front(v);
    }
}

如果你想朝另一个方向旋转，这几乎是交换前后角色的问题。

于 2010-02-03T18:03:19.120 回答
0

如果您的意思是“将第 k 个元素移动到队列的前面”，那么这是一种方法：

void move( int *a, unsigned n, unsigned k )
{ 
    int t; // To store the temporary for the k'th element 

    t = a[ k ];

    // Shift all the elements to the right by one.
    for( unsigned i = k; i > 0; --i )
        a[ i ] = a[ i - 1 ];

    // Put the k'th element at the left of the queue.
    a[ 0 ] = t;
}
于 2010-02-03T18:08:06.940 回答
0 
#include <iostream>
#include <list>
template <typename T>
void Rotate(std::list<T>& list, int k){
    for(int i=0; i<k; ++i){
        T tmp(list.back());
        list.pop_back();
        list.push_front(tmp);
    }
}
int main(){
    std::list<int> ints;
    ints.push_back(1); ints.push_back(2);
    ints.push_back(3); ints.push_back(4);
    Rotate(ints,2);
    for(std::list<int>::const_iterator i = ints.begin(); i!=ints.end(); ++i)
        std::cout << *i << std::endl;
    return 0;
}

将输出：

3
4
1
2
于 2010-02-03T18:19:37.643 回答
0

这个问题很老，但现在似乎最简单的解决方案是依靠std::rotate。复杂度是线性的，但取决于第一个和最后一个之间的距离。因此，如果您需要旋转 1 个元素，复杂度是 O(1)，对于 3，它是 O(3)。

于 2021-01-04T14:29:11.527 回答