[CODEVS3299]有序数组合并求第K大问题

题目描述 Description

给出两个有序数组A和B（从小到大有序），合并两个有序数组后新数组c也有序，询问c数组中第k大的数

假设不计入输入输出复杂度，你能否给出一个O(logN)的方法？

输入描述 Input Description

第一行输入三个整数n、m和k

第二行输入n个用空格隔开的整数表示数组A

第三行输入m个用空格隔开的整数表示数组B

输入保证A和B数组非递减

输出描述 Output Description

合并两个数组之后的第k大的数

样例输入 Sample Input

2 3 4

1 2

1 1 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n,m<=1000000

1<=k <=n+m

思路

不需要O(logN）的复杂度，只需要O(n)的算法即可实现，合并两个数组后求出下标为k的数即可。当然需要考虑数字的重复问题，不过一边循环也可以解决，所以时间复杂度最多为O(kn)，此处数据较弱，不考虑也可过。

var i,j,x:longint;
    kk,n,m,k:int64;
    a,b,c:array[1..10000001] of int64;
begin
    readln(n,m,kk);
    for i:=1 to n do read(a[i]);
    for i:=1 to m do read(b[i]);
    i:=1;//a的指针
    j:=1;//b的指针
    k:=1;//末尾的指针
    while (i<>n+1)and(j<>m+1) do
        begin
            if a[i]<=b[j] then
                begin
                    c[k]:=a[i];
                    inc(i);
                    inc(k);
                end
            else
                begin
                    c[k]:=b[j];
                    inc(j);
                    inc(k);
                end;
        end;
    for x:=i to n do
        begin
            c[k]:=a[x];
            inc(k);
         end;
    for x:=j to m do
        begin
            c[k]:=b[x];
            inc(k);
        end;
    writeln(c[kk]);
end.

View Code