不是VIP会员,不能显示答案

题目解答

题目:
(找第k大的数)给定一个长度为1000000的无序正整数序列,以及另一个数n(1<=n<=1000000),接下来以类似快速排序的方法找到序列中第n大的数(关于第n大的数:例如序列{1,2,3,4,5,6}中第3大的数是4)
Var	 a:array[1..1000000] of integer;
n,m,ans:integer;
procedure swap(var a,b:integer);
var t:integer;
begin
  if  (a<>b) then begin
t:=a; a:=b; b:=t;
end;
end;
Function FindKth(left,right,n:integer):integer;
Var tmp,value,i,j:integer;
begin
  if left=right then exit(left);
  tmp:=random(right-left)+left;
  swap(a[tmp],a[left]);
  value:=  a[left] ;
  i:=left;  j:=right;
while i<j do
  begin
   while (i<j) and ( a[j]<value ) do dec(j);
   if i<j then begin
    a:=a[j];inc(i);
   end else break;
   while (i<j) and ( a[i]>value ) do inc(i);
   if i<j then begin
    a[j]:=a[i]; dec(j);
  end else break;
  end;
   a[i]:=value ;
  if i<n then begin inc(i); exit(FindKth( i,right,n ));end;
  if i>n then begin dec(j); exit( FindKth(left,i,n) );end;
  exit(i);
end;

var i:integer;
begin
  randomize;
   ans:=-1;
m:=5;
for i:=1 to m do
  read(a[i]);
read(n);
ans:=FindKth(1,m,n);
writeln(a[ans]);
end.
考点:
分析:
解答:
评论:
老师: