[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[..] of int64;

begin

    readln(n,m,kk);

    for i:= to n do read(a[i]);

    for i:= to m do read(b[i]);

    i:=;//a的指针

    j:=;//b的指针

    k:=;//末尾的指针

    while (i<>n+)and(j<>m+) 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.

巴特西