PAT 链表倒序的算法优化

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

之前的答案错误问题已经解决了，现在还有运行超时的问题，先贴上之前的代码

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int count, renum;
 8     string add;
 9     cin>>add>>count>>renum;
10     string add1[count],add2[count],madd1[count],madd2[count];
11     int mnum[count],num[count];
12     for(int i=0;i<count;i++)
13     {
14         cin>>add1[i]>>num[i]>>add2[i];
15     }
16     for(int i=0;i<count;i++)
17     {
18 
19         for(int j=0;j<count;j++)
20        {
21            if(add1[j]==add)
22            {
23                madd1[i] = add1[j];
24                mnum[i]=num[j];
25                madd2[i] = add2[j];
26                add=madd2[i];
27                break;
28            }
29        }
30     }
31     int temp=0;
32     int fake = count;
33     while(count-renum>=0)
34     {
35         for(int i= temp,j=temp+renum-1;i<=temp+renum-1;i++,j--)
36         {
37             add1[i] = madd1[j];
38             num[i] = mnum[j];
39         }
40         count-=renum;
41         temp=temp+renum;
42     }
43     for(int i=temp;i<fake;i++)
44     {
45 
46             add1[i] = madd1[i];
47             num[i] = mnum[i];
48     }
49     for(int i=0;i<fake-1;i++)
50     {
51         add2[i]=add1[i+1];
52     }
53     add2[fake-1] = "-1";
54     for(int i=0;i<fake;i++)
55     {
56         cout<<add1[i]<<" "<<num[i]<<" "<<add2[i]<<endl;
57     }
58     return 0;
59 }

　　这个程序的复杂度为o（n*n）,现在想办法降低复杂度，分析可以发现大部分时间是花在将输入数据按顺序排序上，然后我想到如果输入数据的每一行的第一个，和第三个数据真的表示为地址的话，就省去了排序的时间，所以，我们可以开一个10w数组，数组下标表示地址，以此来减少排序时间。具体实现代码如下

 1 #include <iostream>
 2 #include <string.h>
 3 #include <iomanip>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int count ,add,renum;
 9     cin>>add>>count>>renum;
10     int add1[100001],num[100001],add2[100001];
11     for(int i=0;i<=100000;i++)
12     {
13         add1[i]=0;
14         add2[i]=0;
15         num[i]=0;
16     }
17     for(int i=0;i<count;i++)
18     {
19         int a,b,c;
20         cin>>a>>b>>c;
21         add1[a]=a;
22         num[a]=b;
23         add2[a]=c;
24 
25     }
26     add2[100000]=add;
27     int before=100000;
28     int late=-1;
29     int re[renum];
30     int total=0;
31     int sha=100000;
32     while(add2[sha]!=-1)
33     {
34         sha=add2[sha];
35         total++;
36     }
37     int xunh = total/renum;
38     for(int j=0;j<xunh;j++)
39     {
40          int x = add2[before];
41         for(int i=0;i<renum;i++)
42         {
43             re[renum-1-i] = x;
44             x=add2[x];
45             if(i==renum-1)
46             {
47                 late = x;
48             }
49         }
50         add2[before] = re[0];
51         for(int i=0;i<renum-1;i++)
52         {
53             add2[re[i]] = re[i+1];
54         }
55         add2[re[renum-1]] = late;
56         before = re[renum-1];
57     }
58     int m =100000;
59     while(m!=-1)
60     {
61         m=add2[m];
62         if(m!=-1 &&add2[m]!=-1)
63             cout<<setw(5)<<setfill(‘0‘)<<add1[m]<<" "<<num[m]<<" "<<setw(5)<<setfill(‘0‘)<<add2[m]<<endl;
64         else if(m!=-1)
65             cout<<setw(5)<<setfill(‘0‘)<<add1[m]<<" "<<num[m]<<" "<<add2[m]<<endl;
66     }
67     return 0;
68 }