Question

C++超时问题!! 程序运行结果正确，但是时间过长，请帮忙改进, 谢谢!! ；

/*
Name: 1574被涂改的数
Copyright:
Author:
Date: 08/11/14 10:52
Description: 你有一个n个数的数列，数列中0到n-1每个数正好出现了一次。
遗憾的是，有人偷偷地把其中的某两个数改成了-1，现在要你找出他改了哪两个数？
*/
#include<iostream>
using namespace std;
int num[2000000], a[2000000];
void swap(int &a, int &b)
{
if(a>b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
}
int main()
{
int n, ans1, ans2;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>num[i];
}
for(int i=0; i<n; i++)
{
a[i]=i;
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(num[i]!=a[j])
{
num[i]=0; a[j]=0;
}
}
}
for(int i=0; i<n ; i++)
{
if(a[i]!=0)
{ans1=a[i];
a[i]=0;
break;}
}
for(int i=0; i<n ; i++)
{
if(a[i]!=0)
{ans2=a[i];
a[i]=0;
break;}
}
swap(ans1, ans2);
cout<<ans1<<endl<<ans2<<endl;
return 0;
}
P.S 如何改进这个程序... 我应该写得太复杂了....

Answer 1

你这个的复杂度是 n*n+2n了。
根据题目，因为数据时0~n-1,正好是数组下标，因此你只需
a[num[i]]=-2;
这样之后，所有存在的数都变成-2了，遍历a数组，找到不是-2的数，这时候a的下标就是结果了。这样做的程序复杂度是2N，应该就可以了。

追问

那二重循环结构还需要吗? 可以具体写一下需要修正的程序吗? 谢谢了! 初学者还是不太懂!!

追答

#include<iostream>
using namespace std;
void swap(int &a, int &b)
{
if(a>b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
} 
int main()
{
// int num[2000000], a[2000000];
int n;//, ans1, ans2;
int i,*num,*a;
cout<<"输入总数n：";
cin>>n;
num = new int[n];
a = new int[n];
cout<<"输入数列："<<endl;
for(i=0; i<n; i++)
{
cin>>num[i];
}
for(i=0; i<n; i++)
{
a[i]=i; 
}
//     for(int i=0; i<n; i++)
//     {
//         for(int j=0; j<n; j++)
//         {
//  if(num[i]!=a[j])
//  {
//  num[i]=0;  a[j]=0;
//  }
//         }
//     }
    for(i=0;i<n ; i++)
    {
//  if(a[i]!=0)
//  {ans1=a[i];
//  a[i]=0;
//  break;}
if(num[i]>=0&&num[i]<n)//not -1
a[num[i]]=-2;
    }
cout<<"排除数是："<<endl;
    for( i=0; i<n ; i++)
    {
//  if(a[i]!=0)
//  {ans2=a[i];
//  a[i]=0;
//  break;}
if(a[i]>-2)
cout<<a[i]<<endl;
    }
//    swap(ans1, ans2);不需要了，因为a是顺序数列
//    cout<<ans1<<endl<<ans2<<endl;
delete[] num;
delete[] a;
    return 0;
}

Answer 2

qsort一下num，然后挨个找，看看那两个数字被跳过了。。。
时间复杂度应该是 n log n