1067. Sort with Swap(0,*) (25)

系统管理员 2022-08-13 18:32 103阅读 0赞

下面是自己写的，但是只得了19分，有两个点超时

<span style="font-size:14px;">#include<iostream>
    using namespace std;
    //这样写会超时
     void swap(int *x,int *y)
     {
    	 int temp;
         temp=*x;
         *x=*y;
         *y=temp;
     }
     int find(int *arr,int begin,int end)
     {
    	 for(int i=begin;i<end;i++)
    	 {
    		 if(arr[i]!=i)return i;
    	 }
    	 return 0;
     }
     int main()
     {
        int n;
    	int num[100002];
    	int firstPos=1;
    	int i,j,index0;
    	bool flag=true;
    	int count=0;
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    	    cin>>num[i];
    
    	}
    	for(i=0;i<n;i++)
    	{
    		if(num[i]==0)
    		{
    			index0=i;
    			break;
    		}
    	}
    	while(flag)
    	{
    	    flag=false;
    	if(index0!=0)
    	{
    	   
    	   for(j=0;j<n;j++)
    	   {
    		   if(num[j]==index0)
    		   {
    				swap(&num[j],&num[index0]);
    				index0=j;
    			    count++;
    				flag=true;
    				break;
    			}
    		}
    	}
    	else
    	{
    	    for(i=1;i<n;i++)
    		{
    		    if(num[i]!=i)
    			{	 
    			    swap(&num[0],&num[i]);
    				index0=i;
    				count++;
    				flag=true;
    				break;
    			}
    		}
    	}
    	}
    	cout<<count<<endl;
    	system("pause");
    	return 0;
     }</span>

下面是参考别人的代码。测试点全部通过，但是逻辑有点绕不清，注意赋值的方式

num[t]=i

#include<iostream>
    using namespace std;
     int find(int *arr,int begin,int end)
     {
    	 for(int i=begin;i<end;i++)
    	 {
    		 if(arr[i]!=i)return i;
    	 }
    	 return 0;
     }
     int main()
     {
        int n;
    	int num[100002];
    	int firstPos=1;
    	int i,j,t,temp;
    	bool flag=true;
    	int count=0;
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    	    cin>>t;
    		num[t]=i;
    	}
    	firstPos=find(num,firstPos,n);
    	while(firstPos)
    	{
    		if(num[0]==0)
    		{
    			num[0]=num[firstPos];
    			num[firstPos]=0;
    			count++;
    		}
    		while(num[0]!=0)
    		{
    			temp=num[0];
    			num[0]=num[temp];
    			num[temp]=temp;
    			count++;
    		}
    		firstPos = find(num,firstPos,n);
    	}
    	cout<<count<<endl;
    	system("pause");
    	return 0;
     }