c – 以预先指定的顺序随机播放数组变量,而不使用“输入数组大小

发布时间：2020-12-16 09:30:20 所属栏目：百科来源：网络整理

导读：输入： A[4] = {0,4,-1,1000} - Actual Array P[4] = {1,3,2} - Order to be reshuffled 输出： A[4] = {4,1000,-1} 条件：不要使用其他数组作为内存.可以使用额外的变量或两个. 问题：我在C中有以下程序,但是对于数组P的某些输入,这会失败. #includeiostrea

输入：

A[4] = {0,4,-1,1000} - Actual Array
  P[4] = {1,3,2} - Order to be reshuffled

输出：

A[4] = {4,1000,-1}

条件：不要使用其他数组作为内存.可以使用额外的变量或两个.

问题：我在C中有以下程序,但是对于数组P的某些输入,这会失败.

#include<iostream>

using namespace std;

void swap(int *a_r,int *r)
{
    int temp = *r;
    *r = *a_r;
    *a_r = temp;
}
int main()
{
    int A[4] = {0,1000};
    int P[4] = {3,1,2};
    int value = A[0],dest = P[0];

    for(int i=0; i<4;i++)
    {
        swap(&A[dest],&value);
        dest = P[dest];
    }
    for(int i=0;i<4;i++)
        cout<<A[i]<<" ";
}

解决方法

首先,我真的很喜欢Jonathan的解决方案,但我觉得我也可以添加一些有趣的想法.

主要观察是阵列P由几个循环组成.
我们考虑p = {1,2,5}.有三个循环：0 => 1 => 4 => 0,2 => 3 => 2和5 => 5.要在一个循环旁边替换变量,我们根本不需要额外的内存.我们就像这样经历它

do {
    a[i] = a[p[i]];
    i = p[i];
} while (i != first_i);

(不过,最后一个元素需要特别注意.)完整的工作版本：

for (int i = 0; i < n; ++i) {
        if (p[i] < 0) {
            // been at index 'i' already
            continue;
        }

        // new loop found
        int j = i;
        int first_value = a[i]; // to be put in last position in the chain
        int prev_j; // we always store previous 'j' index
        do {
            a[j] = a[p[j]];

            prev_j = j;
            j = p[j]; // move to next 'j'
            p[prev_j] = -1; // mark element as processed
        } while (i != j);
        a[prev_j] = first_value;
    }

我的解决方案唯一的问题是它使用p数组将元素标记为“已处理”.一些采访者可能认为没问题,其他人 – 不是,取决于他们想到的解决方案.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!