[转载]寻找两个有序数组中的第K个数或者中位数
2024-10-18 22:36:37
http://blog.csdn.net/realxie/article/details/8078043
假设有长度分为为M和N的两个升序数组A和B,在A和B两个数组中查找第K大的数,即将A和B按升序合并后的第K个数。
解法一:
使用两个指针指向A和B的开头,很容易在O(M+N)的时间内完成,此算法略过。
解法二:
使用二分的方法。算法思想在代码注释中
- #include <iostream>
- #include <string.h>
- #include <stdlib.h>
- using namespace std;
- //Notice : K > 0
- int FindKthElm(int A[], int aBeg, int aEnd, int B[], int bBeg, int bEnd, int k)
- {
- if (aBeg > aEnd)
- {
- return B[bBeg + k - 1];
- }
- if (bBeg > bEnd)
- {
- return A[aBeg + k - 1];
- }
- //取中间位置
- int aMid = aBeg + (aEnd - aBeg)/2;
- int bMid = bBeg + (bEnd - bBeg)/2;
- //从A和B的开始位置到两个数组中间位置的元素个数
- int halfLen = aMid - aBeg + bMid - bBeg + 2;
- if (A[aMid] < B[bMid])
- {
- if (halfLen > k)
- {
- // 此时在合并的数组中A[aBeg...aMid]和元素一定在B[bMid]的左侧,
- // 即此时第k大的元素一定比B[bMid]这个元素小(严格来说不大于)
- // 故以后没有必要搜索 B[bMid...bEnd]这些元素
- return FindKthElm(A, aBeg, aEnd, B, bBeg, bMid - 1, k);
- }
- else
- {
- // 此时在合并的数组中A[aBeg...aMid]元素一定在B[bMid]的左侧,
- // 所以前K个元素中一定包含A[aBeg...aMid](可以使用反证法来证明这点)。
- // 但是无法判断A[amid+1...aEnd]与B[bBeg...bEnd]之间的关系,帮需要对他们进行判断
- // 此时K就剩下除去A[aBeg...aMid]这些元素,个数为k - (aMid - aBeg + 1)
- return FindKthElm(A, aMid + 1, aEnd, B, bBeg, bEnd, k - (aMid - aBeg + 1));
- }
- }
- else
- {
- //注释与上面相似
- if (halfLen > k)
- {
- return FindKthElm(A, aBeg, aMid - 1, B, bBeg, bEnd, k);
- }
- else
- {
- return FindKthElm(A, aBeg, aEnd, B, bMid + 1, bEnd, k - (bMid - bBeg + 1));
- }
- }
- }
- int main()
- {
- const int ALen = 11;
- const int BLen = 5;
- int apos = 0;
- int bpos = 0;
- int A[ALen];
- int B[ALen];
- //生成两个递增数组A 和 B
- for (int i = 1; i <= ALen + BLen; ++i)
- {
- if (apos >= ALen)
- {
- B[bpos++] = i;
- }
- else if (bpos >= BLen)
- {
- A[apos++] = i;
- }
- else
- {
- if (rand()%2 == 1)
- {
- A[apos++] = i;
- }
- else
- {
- B[bpos++] = i;
- }
- }
- }
- //输出A和B的内容
- for (int i = 0; i < ALen; ++i)
- {
- cout <<A[i] <<" ";
- }
- cout <<endl;
- for (int i = 0; i < BLen; ++i)
- {
- cout <<B[i] <<" ";
- }
- cout <<endl;
- //验证每个K是不是正解
- for (int i = 1; i <= ALen + BLen; ++i)
- {
- cout << i <<" : "<<FindKthElm(A, 0 , ALen - 1, B, 0 , BLen - 1, i)<<endl;
- }
- return 0;
- }
最新文章
- EQueue 2.0 性能测试报告
- Ubuntu 杂音 alsa*
- Visual Studio开发Cordova应用示例
- AngularJs $interval 和 $timeout
- Echarts - js
- Android apk 的安装过程
- java 下载文件功能代码例子
- 连载:面向对象葵花宝典:思想、技巧与实践(32) - LSP原则
- arm-linux-gcc编译器定义寄存器变量
- 使用blktrace统计磁盘块I/O访问频率 + IO调度CFQ
- 欢迎大家Follow me!微软MVP罗勇(Dynamics CRM方向)欢迎您!
- hdu 1150 Machine Schedule 最小覆盖点集
- jQuery 属性(十二)
- 图书馆管理系统(C语言)
- zabbix自定义模板——监控TCP连接状态
- jemter的使用
- input错误提示,点击提交,提示有未填项,屏幕滑到input未填项的位置
- Go语言学习笔记(一)Let&#39;s 干吧
- php的一个验证邮箱的正则表达式
- arcgis求邻接矩阵
热门文章
- PCRE安装
- WPF学习开发客户端软件-任务助手(下 2015年2月4日代码更新)
- Try..Finally..相信自己的眼睛
- 深入理解java虚拟机【Java Class类文件结构】
- 微软BI 之SSIS 系列 - 使用 Script Component Destination 和 ADO.NET 解析不规则文件并插入数据
- YUI Compressor for Sublime text2
- atitit.hbnt orm db 新新增更新最佳实践o99
- atitit.提升开发效率---mda 软件开发方式的革命--(2)
- Rails下cloud datastore的使用
- iOS-常用的辅助工具软件