Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:O(n)的算法怎么也要32MS

Posted by 1141482126 at 2012-12-29 15:33:52 on Problem 2388
In Reply To:O(n)的算法怎么也要32MS Posted by:love_mely at 2012-12-28 09:16:48
> #include<iostream>
> #include<algorithm>
> #include<time.h>
> using namespace std;
> int n;
> int* milk;
> void swap(int i,int j)
> {
> 	int temp=milk[i];
> 	milk[i]=milk[j];
> 	milk[j]=temp;
> }
> int findKth(int start,int end,int k)
> {
> 	if(start>= end)
> 		return milk[start];
> 	srand((unsigned)time(NULL));
> 	int index=(rand() % (end-start)) + start;
> 	int key=milk[index];
> 	swap(start,index);
> 
> 	int i=start;
> 	int j=end;
> 	while(i!=j)
> 	{
> 		while(j!=i)
> 		{
> 			if(milk[j]>=key)
> 				j--;
> 			else
> 			{
> 				swap(i,j);
> 				break;
> 			}
> 		}
> 		while(i!=j)
> 		{
> 			if(milk[i]<=key)
> 				i++;
> 			else
> 			{
> 				swap(i,j);
> 				break;
> 			}
> 		}
> 	}
> 	if(i+1==k)
> 		return milk[i];
> 	else if(i+1 > k)
> 		return findKth(start,i-1,k);
> 	else
> 		return findKth(i+1,end,k);
> }
> int main(void)
> {
> 	cin>>n;
> 	milk=new int[n];
> 	for(int i=0;i<n;i++)
> 		cin>>milk[i];
> 	int k=n/2+1;
> 	int result=findKth(0,n-1,k);
> 	cout<<result<<endl;
> 	system("pause");
> 	return 0;
> }
抱歉,你的算法的思想是什么呢?我没有看懂。。。不过能到O(n)的时间真的很了不起!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator