在两个有序数列中寻找第k小的元素
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
本篇文章探讨了如何在两个已排序的数组中高效地查找第k小的元素，提供了多种算法解决方案。
已知两个已经排好序（非减序）的序列X和Y 其中X的长度为m Y长度为n 现在请你用分治算法 找出X和Y的第k小的数，要求时间复杂度为O(max{log m, log n})。不使用将两个序列合并后查找第k小元素的方法（该方法的时间复杂度为O(m + n)），而是充分利用序列已排序的特点。
输入格式：第一行包含三个整数m、n和k，分别表示X的长度、Y的长度以及需要找到的是第几个最小值。这三个数值之间以空格分隔。(1 < m, n < 100000; 1< k < m+n)。
第二行为序列X中的m个非减序排列的整数。
第三行包含n个非递减排列的整数，构成序列Y。
输出格式：计算并打印出两个排序好的序列X和Y合并后的第k小数字。
示例输入：
```
5 6 7
1 8 12 12 21
4 12 20 22 26 31
```
示例输出：
```
20
```
全部评论 (0)
还没有任何评论哟~
