两个有序数组中查找第K大数

题目:两个数组A、B,长度分别为m、n,即A(m)、B(n),分别是递增数组。求第K大的数字。

方法一:

简单的办法,使用Merge Sort,首先将两个数组合并,然后在枚举查找。这个算法的时间复杂度是O(m+n)、空间复杂度也是O(M+n)。

这个方法其实没有考虑到有第K大数为两个相同数字的情况。

方法二:

这里需要两个前提条件,

1、如果K是中位数,则(M+n)是奇数还是偶数是有关系的。如果是奇数,那么中位数唯一,如果是偶数就有两个中位数,可以随便取一个。

2、如果找到的第K大数是x,假如在A的位置是A(x),在B中的位置是B(x),则Ax+Bx-1=k是成立的。

接下来是具体实现逻辑:

1、首先假设K大数在A数组中,首先检查 (m/(m+n))*(k-1),假设其值为A1。然后检查B中(k+1-(n/(m+n))*(k-1))假设为B1,检查A1、B1是否相等,或者大于B中的第(k+1-(n/(m+n))*(k-1)),并且小于(k+1-(n/(m+n))*(k-1))+1个元素。满足条件就可以知道A1就是所求,否则看条件2。

2、如果两个条件都不满足,那么需要判断第K个元素是位于A1左边还是右边。

如果A1>B1,那么K肯定不在A[0, (m/(m + n)) * (k - 1)]以及B[(k + 1 - (m/(m + n)) * (k - 1))+ 1, n]中;

如果A1<B1,那么K肯定不在A[ (m/(m + n)) * (k - 1), m]以及B[0, (k + 1 - (m/(m + n)) * (k - 1))]中。

第K个元素有可能在B中,同理可以假设在B中,再进行一次搜索。复杂度为log(m)+log(n)。

具体代码如下:

int kthsmallest(int *a,int m,int *b,int n,int k) { 
        if (m == 0) {
            return b[k - 1];
        }
        if (n == 0) {
            return a[k - 1];
        }
        if (k == 1) {
            return (a[0] < b[0])?a[0]:b[0];
        }
        if (k == m + n) {
            return (a[m - 1] > b[n - 1])?a[m - 1]:b[n - 1];
        }
        int i = ((double) m) / (m + n) * (k - 1);
        int j = k - 1 - i;
        if (j >= n) {
            j = n - 1;
            i = k - n;
        }
        if (((i == 0) || (a[i - 1] <= b[j])) && (b[j] <= a[i])) {
            return b[j];
        }
        if (((j == 0) || (b[j - 1] <= a[i])) && (a[i] <= b[j])) {
            return a[i];
        }
        if (a[i] <= b[j]) {
            return kthsmallest(a + i + 1, m - i - 1, b, j, k - i - 1);
        } else {
            return kthsmallest(a, i, b + j + 1, n - j - 1, k - j - 1);
        }
    }

方法三:

当然也可以在方法一的基础上,采用一些二分的办法进行优化,但是这种算法

参考资料:

1、http://www.cnblogs.com/davidluo/articles/k-smallest-element-of-two-sorted-array.html

2、http://blog.csdn.net/realxie/article/details/8078043

3、http://blog.csdn.net/shifuwawa/article/details/6121573

4、http://eriol.iteye.com/blog/1172098

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]统计字符

这也是一道字符串类型中比较常规的题(但含自定义函数哦),但前提得知道一个函数哦,就会简单很多!!! 如果你不知道,写完这题你就知道了哦!!! 题目描述 编写一...

37880
来自专栏Java编程

四道Java基础题,你能对几道?

如果这道题你能得出正确答案,并能了解其中的原理的话。说明你基础还可以。如果你的答案 是 true 和true的话,你的基础就有所欠缺了。

1.1K10
来自专栏chenjx85的技术专栏

leetcode-67- Add Binary

34660
来自专栏决胜机器学习

有趣的算法(七) ——快速排序改进算法

有趣的算法(七) ——快速排序改进算法 (原创内容,转载请注明来源,谢谢) 一、概述 快速排序,被认为是最好的排序算法之一。快速排序是20世纪60年代被提出...

33440
来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

361100
来自专栏Python小屋

Python内置函数iter()语法及应用

iter()函数用来返回指定对象的迭代器,有两种用法:iter(iterable)和iter(callable, sentinel),前者要求参数必须为序列或者...

38460
来自专栏数据小魔方

左右用R右手Python系列——字符串格式化输出

学习Python不到一个月,虽然学的很渣,但是还是想通过这种途径分享自己的学习心得,毕竟当初学习R语言也是这么走过来的。 今天是R语言与Python综合系列的第...

45460
来自专栏诸葛青云的专栏

C语言for语句用法详解

在C语言中,for语句使用最为灵活,它完全可以取代 while 语句。它的一般形式为:

9600
来自专栏chenjx85的技术专栏

leetcode-551-Student Attendance Record I(判断是否出现连续几个相同字符)

15360
来自专栏小筱月

各种排序算法

冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

17930

扫码关注云+社区

领取腾讯云代金券