每天一道算法题目(18)——取等长有序数组的上中位数和不等长有序数组的第k小的数
1.取上中位数
题目:
给定两个有序数组arr1和arr2,两个数组长度都为N,求两个数组中所有数的上中位数。要求:时间复杂度O(logN)。
例如:
arr1 = {1,2,3,4};
arr2 = {3,4,5,6};
一共8个数则上中位数是第4个数,所以返回3。
arr1 = {0,1,2};
arr2 = {3,4,5};
一共6个数则上中位数是第3个数,所以返回2。
思路:
(1)假设两个数组长度为偶数,取中间节点index=1
1 2 3 4
1‘ 2’ 3‘ 4’
若2 == 2‘ ,则直接返回;
若2 > 2', 说明 2 至少排第4, 所以3,4可以排除,1’ 2‘(2’ 最多排第3)可以排除,所以对剩下的1 2和3‘ 4’ 递归
若2 < 2‘,同理递归1’ 2‘和3、4.
(2)假设两个数组长度为奇数,取中间节点index=2.
1 2 3 4 5
1‘ 2’ 3‘ 4’ 5’
若3 == 3‘ ,则直接返回;
若3 > 3', 说明 3 至少排第6, 所以4,5可以排除,1’ 2‘(2’ 最多排第4)可以排除,所以对剩下的1 2 3和 3‘ 4’ 5‘递归,其实3也能排除,但是为了保证两个数组的长度一样,保留3
若3 < 3‘,同理递归1’ 2‘ 3’和3、4 、5.
代码:
int getUpMedian(const vector<int> & arr1, int start1, int end1,const vector<int> & arr2, int start2, int end2) { if(start1 == end1)
return min(arr1[start1], arr2[start2]); int size = end1-start1+1;
int halfSize; if(size&1 == 1)//奇
halfSize = (size + 1)/2;
else//偶
halfSize = size/2; if(arr1[start1+halfSize - 1] == arr2[start2 + halfSize - 1])
return arr1[start1 + halfSize - 1];
else if(arr1[start1 + halfSize - 1] > arr2[start2 + halfSize - 1])
return getUpMedian(arr1,start1,start1+halfSize-1,arr2,end2-(halfSize-1),end2);
else
return getUpMedian(arr1,end1-(halfSize-1),end1,arr2,start2,start2+halfSize -1);
} int getUpMedian(vector<int> arr1, vector<int> arr2) {//主函数 if(arr1.size() != arr2.size())
return -1;
if(arr1.size() == 0)
return -1;
return getUpMedian1(arr1,0,arr1.size()-1,arr2,0,arr1.size() -1 );
}
2.取不等长有序数组的最小K个数
题目:
给定两个有序数组arr1和arr2,在给定一个整数k,返回两个数组的所有数中第K小的数。要求:如果arr1的长度为N,arr2的长度为M。要求时间复杂度达到O(log(min{M,N}))
例如:arr1 = {1,2,3,4,5};arr2 = {3,4,5};K = 1; 因为1为所有数中最小的,所以返回1;
arr1 = {1,2,3};arr2 = {3,4,5,6};K = 4;因为3为所有数中第4小的数,所以返回3;
思路:
分三种情况考虑,假设arr1的长度N小于等于arr2的长度M
(1)若K<=N
结果为 arr1[0---K-1]和arr2[0---K-1]取中位数
(2)若 N<K<=M。先将arr2分为[0--K-N-1],[K-N-----K-1],[K,M-1]三部分
当arr2[K-N-1]>=arr1[N-1],结果为arr2[K-N-1]
否则,arr2[0--K-N-1]部分的所有数据一定至多在K-1位置(极端情况下,arr1[N]占据K位置)。而arr2[K,M-1]区间段的元素至少在K+1位置。因此结果对长度为N的两段区间段arr1[0,N-1]和arr2[K-N,K-1]取中位数即可。
(3)若K>M>N。先将划分arr1[0,K-M-1][K-M,N-1]两段区间,arr2[0,K-N-1][K-N,M-1]
当arr2[K-N-1]>=arr1[N-1],结果为arr2[K-N-1]
当arr1[K-M-1]>=arr2[M-1],结果为arr1[K-M-1]
两者不满足的话。则如前所叙述,arr1[0,K-M-1]和arr2[0,K-N-1]的元素都在位置K之前,至多为K-1。因此结果为长度为M+N-K的两段区间arr1[K-M,N-1]和arr2[K-N,M-1]的中位数。
时间复杂度最大为情况(2),即为所要求。
代码:
int findKthNum(vector<int> arr1, vector<int> arr2, int kth)
{
int size1 = arr1.size();
int size2 = arr2.size(); if(size1 > size2)
return findKthNum(arr2, arr1, kth);//ensur if(kth <= size1)
return getUpMedian(arr1, 0, kth - 1, arr2, 0, kth - 1);//前k个,取中位数即可
else if (kth <= size2 && kth > size1)
{
if(arr2[kth - size1 - 1] >= arr1[size1 - 1] )
return arr2[kth - size1 - 1];
else
return getUpMedian(arr1, 0, size1-1, arr2, kth-size1, kth-1);
}
else
{
if(arr2[kth-size1-1] >= arr1[size1-1])
return arr2[kth-size1-1];
if(arr1[kth-size2-1] >= arr2[size2-1])
return arr1[kth-size2-1];
return getUpMedian(arr1, kth-size2, size1-1, arr2, kth-size1, size2-1);
} }
参考:
1.[nowCoder] 两个长度相同有序数组的中位数
最新文章
- apache配置 php中没有php5apache2_4.dll
- ToolWindow工具类
- Pycharm快捷方式
- Linux 多线程编程
- Java 修改Windows注册表,以实现开机自启动应用程序。
- 随堂练习——Rational rose
- Android中mesure过程详解
- MapReduce基础
- TFS服务器(微软源代码管理服务器)上彻底删除项目
- Spring 中JCA CCI分析--转载
- 复制文件时,如何显示进度条(使用BlockRead函数读取数据,并插入application.ProcessMessages)
- ssh 实体关系分析确立(ER图-实体关系图)
- 使用Nginx+CppCMS构建高效Web应用服务器
- form表单提交图片禁止跳转
- Android手机客户端测试点(全)
- HTML meta refresh 刷新与跳转(重定向)页面
- [转]Nginx基本功能极速入门
- &#183;c#之Thread实现暂停继续(转)
- ZooInspector 连接不到 Zookeeper 的解决方法
- [LeetCode] Flatten a Multilevel Doubly Linked List 压平一个多层的双向链表