C/C++语言算法题——替换

浏览数：32 / 时间：2015年06月08日

【问题】

Description

给定一个有限长度的非负整数序列。一次操作是指从第一个元素开始，依次把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。总有一个时刻该数列将不再发生改变（即此时每个数都恰好等于它右边比它小的数的个数）。例如给定数列：
5, 44, 19, 6, 49, 1, 27, 19, 50, 20
连续进行五次操作后，依次得到新数列如下：

1, 6, 2, 1, 4, 0, 2, 0, 1, 0
3, 8, 5, 3, 5, 0, 3, 0, 1, 0
4, 8, 6, 4, 5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1, 0

其中，第四次操作后，数列不再发生改变。
对给定数列，循环执行上述操作，直到其不再改变为止，输出最后得到的数列。

Input

第1行：一个整数T（1≤T≤10）为问题数。
对于每组测试数据：
第1行是一个正整数：数列长度N ( 2 < N≤30 )；
第2行有N个正整数：分别为该数列第1至第N个元素的值a1,a2,…,aN( a1,a2,…, aN均为1 - 1000的数)，每两个整数之间用一个空格分开。

Output

对于每个问题，输出一行问题的编号（0开始编号，格式：case #0: 等）。
然后在一行中依次输出最后数列的所有元素，每两个元素之间用一个空格分开，最后一个元素后面没有空格。

Sample Input

3
10
5 44 19 6 49 1 27 19 50 20
10
3 2 7 10 9 8 8 5 1 5
10
12 12 19 19 7 10 9 6 18 9

Sample Output

case #0:
5 8 7 5 5 0 3 0 1 0
case #1:
9 2 3 6 5 3 3 2 0 0
case #2:
6 6 6 6 3 4 3 0 1 0

【解题报告】

算法本身很容易实现，但是问题是我不清楚应当如何判断算法何时结束，也就是如何判断“两次变换所得到的新数组相等”。如果有更好的算法请不吝赐教。

  1 #include <iostream>
  2 using namespace std;
  3 #define TRUE 1
  4 #define FALSE 0
  5 
  6 int isSame(const int*, const int*, const int);
  7 void setArray(int*, int);
  8 void outputArray(const int*, const int);
  9 void process(int*, int);
 10 int* clone(const int*, int);
 11 
 12 int main()
 13 {
 14     int T;
 15     cin>>T;
 16     for(int c = 0; c < T; c++)
 17     {
 18         int N;
 19         cin>>N;
 20         int* arr = new int[N];
 21         setArray(arr,N);
 22         for(;;)                            /* 这里我实在想不出该如何简便地判断参加变换的数组是否发生变化，因此 */
 23         {                                /* 只能通过备份前一次变换的结果和当次运算结果作比较 */
 24             int* temp = clone(arr,N);   
 25             process(arr,N);                /* 虽然能够AC，但是这肯定不是最优的算法 */
 26             if(isSame(arr,temp,N))      /* 因此如有更好的，时间复杂度更低的算法还望不吝赐教奥 */
 27             {
 28                 delete[] temp;
 29                 break;
 30             }
 31         }
 32         cout<<"case #"<<c<<":"<<endl;
 33         outputArray(arr,N);
 34         delete[] arr;
 35     }
 36     return 0;
 37 }
 38 
 39 /** 判断两个同等长度的数组是否相等
 40   @param arr1 数组1
 41   @param arr2 数组2
 42   @param N 数组1和2的长度
 43   @returns 相等返回1，否则返回0
 44 */
 45 int isSame(const int* arr1, const int* arr2, const int N)
 46 {
 47     for(int i = 0; i < N; i++)
 48     {
 49         if(arr1[i] != arr2[i])
 50             return FALSE;
 51     }
 52     return TRUE;
 53 }
 54 
 55 /**
 56  通过标准输入设置数组的各元素
 57  @param arr 待填充的数组
 58  @param n   数组长度
 59 */
 60 void setArray(int* arr, int n)
 61 {
 62     int t;
 63     for(int i = 0; i < n; i++)
 64     {
 65         cin>>t;
 66         arr[i] = t;
 67     }
 68 }
 69 
 70 /**
 71   输出数组
 72   @param arr 要输出的数组
 73   @param N 数组长度
 74 */
 75 void outputArray(const int* arr, const int N)
 76 {
 77     for(int i = 0; i < N; i++)
 78     {
 79         cout<<arr[i];
 80         if(i != N-1) cout<<‘ ‘;
 81         else cout<<‘\n‘;
 82     }
 83 }
 84 
 85 /**
 86   处理算法
 87   循环处理每一个元素，将其修改为它后面比它小的元素的个数
 88   @param arr 要处理的数组
 89   @param N 数组长度
 90 */
 91 void process(int* arr, int N)
 92 {
 93     for(int i = 0; i < N; i++)
 94     {
 95         int count = 0;
 96         for(int j = i+1; j < N; j++)
 97         {
 98             if(arr[j] < arr[i])
 99                 count++;
100         }
101         arr[i] = count;
102     }
103 }
104 
105 /**
106   克隆数组，将一个数组克隆为另一个数组，
107   使得两个数组中的各元素相同，但他们的首指针不同。
108   @param arr 待克隆的源数组
109   @param N   数组长度
110   @returns   克隆出的新数组
111 */
112 int* clone(const int* arr, int N)
113 {
114     int* temp = new int[N];
115     for(int i = 0; i < N; i++)
116     {
117         temp[i] = arr[i];
118     }
119     return temp;
120 }解题代码

解题代码

【优化】

根据hoodlum1980的建议。将process函数改为

bool process(int* arr, int N)
{
    bool changed = false;
    for(int i = 0; i < N; i++)
    {
        int count = 0;
        for(int j = i+1; j < N; j++)
        {
            if(arr[j] < arr[i])
                count++;
        }
        if(arr[i] != count)
        {
            arr[i] = count;
            changed = true;
        }
    }
    return changed;
}