本关任务:一个长度为L(L≥1)的升序序列S,处在第L/2(若为小数则去掉小数后加1)个位置的数称为S的中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。现有两个等长升序序列A和B,试实现一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。 编程要求 输入 多组数据,每组数据有三行,第一行为序列的长度n,第二行为序列A的n个元素,第三行为序列B的n个元素(元素之间用空格分隔)。当n=0时输入结束。 输出 对于每组数据分别输出两个序列的中位数,占一行。 测试说明 平台会对你编写的代码进行测试: 测试输入: 5 11 13 15 17 19 2 4 6 8 20 6 1 2 3 4 5 6 7 8 9 10 11 12 0 预期输出: 11 6
时间: 2025-03-12 19:03:45 浏览: 51
为了高效地找到两个等长升序序列 A 和 B 的中位数,我们可以采用二分查找的思想,在 O(log n) 时间复杂度内解决问题。
### 算法思路:
1. **特殊情况处理**:
- 如果 `n = 0` 直接返回。
2. **双指针合并找中位数**:
- 因为序列已经是有序的,并且长度相等,我们可以通过比较两数组当前考察元素大小的方式来模拟归并排序的过程而不需要额外的空间存储新的列表。仅需要记录遍历过程中到达中间位置的那个值即可。
- 定义两个索引 i, j 分别指向A、B的第一个元素;同时定义变量k用于跟踪已经经过了多少个数字以及last保存上一次访问的有效数值(即可能是最终结果之一)。
- 每次迭代选择较小的一个前进直至达到一半的位置(对于偶数总长度而言需再进一步确认紧跟其后的那个数以确定确切的答案)。
3. **直接定位中点元素(更优解法)**
- 利用二分搜索递归减少待考虑范围直到一边全部小于另一边最小值为止,则另一侧对应的下标就是所求答案所在之处。(该方法可以保证O(log(min(m,n)))效率)
下面是基于第二种较为直观易懂的方法Python代码示例:
```python
def findMedianSortedArrays(nums1, nums2):
total_length = len(nums1)
if not total_length:
return
# Initialize pointers for both arrays and a counter variable k.
i, j, last = 0, 0, None
mid_index = (total_length * 2 + 1) // 2
while True:
# If one array is fully traversed then take from other directly.
if i == total_length:
current = nums2[j]
j += 1
elif j == total_length:
current = nums1[i]
i += 1
else: # Choose the smaller value to move forward.
if nums1[i] < nums2[j]:
current = nums1[i]
i += 1
else:
current = nums2[j]
j += 1
# Update 'last', which keeps track of potential median candidate.
last = current
# Stop when we've reached or passed half way point in combined lists.
if ((i+j)==mid_index): break
print(last)
# Reading multiple test cases until end-of-file condition met.
import sys
input_data = iter(sys.stdin.read().strip().split('\n'))
while True:
try:
n = int(next(input_data))
if n==0 :break
arr_a=list(map(int,next(input_data).split()))
arr_b=list(map(int,next(input_data).split()))
findMedianSortedArrays(arr_a,arr_b)
except Exception as e :
break
```
此程序实现了对给定问题的要求,并能够有效地计算出两个已排序数组之间的中位数。需要注意的是,这个解决方案假设输入的数据格式是正确的并且只包含正整数。
阅读全文