首页 > 试题广场 >

Median

[编程题]Median
  • 热度指数:3217 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the non-decreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.     Given two increasing sequences of integers, you are asked to find their median.

输入描述:
    Each input file may contain more than one test case.
    Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤1000000) is the size of that sequence. Then N integers follow, separated by a space.
    It is guaranteed that all the integers are in the range of long int.


输出描述:
    For each test case you should output the median of the two given sequences in a line.
示例1

输入

4 11 12 13 14
5 9 10 15 16 17

输出

13
超高效算法,时间复杂度为O(log(n)),n为两个数组长度的最小值;并未改变数组,空间就多出几个中间值。
百万级别的数据,内存都40000K了,时间才272ms,使用c/c++岂不是更快(*^▽^*)
思路:假设array1数组长度比较小,通俗易懂地讲:数组已经排好序了,就是在array1中找出从哪个元素开始分给右边合适,这其中一直保持两边元素均分(array2会给元素左边以达到均分),只要查找,不需要移动。所以达到二分查找的速度。(看着下方表格比较好理解)
def getMedianNum(array1, array2):
    array_len_1 = len(array1)
    array_len_2 = len(array2)
    if array_len_1 > array_len_2:     #保持array1为数组长度小的那个
        array_len_1, array_len_2, array1, array2= array_len_2, array_len_1, array2, array1
    indexMin = 0        #在array1中查找的左下标
    indexMax = array_len_1    #在array1中查找的右下标
    mid_len = (array_len_1 + array_len_2 + 1) // 2  #在这里把数组个数平均分,如果为奇数,则左边多一个
    while indexMin <= indexMax:
        leftIndex = (indexMax + indexMin) // 2  #这个是array1分到左边元素的个数,在此一直二分查找
        rightIndex = mid_len - leftIndex    #这个是array2分到左边元素的个数,所以这里一直保持着左右平均分数组
        #leftIndex+rightIndex一直等于mid_len
        #如果第二个数组分到左边的最大数比第一个数组分到右边的最小数要大
        if leftIndex < array_len_1 and array2[rightIndex - 1] > array1[leftIndex]:
            #则分割数组,array要从左边拿回来一点元素(上面有保持平分数组)
            #分割leftIndex都不满足了,那么就在leftIndex+1的右边继续查找
            indexMin = leftIndex + 1
        #如果第一个数组在左边的最大数比第二个数组在左边的最小数要大
        elif leftIndex > 0 and array1[leftIndex - 1] > array2[rightIndex]:
        #则分割数组,array1要给多一点右边元素
        #leftIndex都不满足了,那么只能在leftIndex-1的左边继续查找
            indexMax = leftIndex - 1
        else:
            if leftIndex == 0:
                max_of_left = array2[rightIndex - 1]
            elif rightIndex == 0:
                max_of_left = array1[leftIndex - 1]
            else:
                max_of_left = max(array1[leftIndex - 1], array2[rightIndex - 1])
            return max_of_left

try:
    while True:
        array1 = list(map(int,input().split()))
        array2 = list(map(int,input().split()))
        print(getMedianNum(array1[1:],array2[1:]))
except Exception:
    pass

编辑于 2018-09-20 17:48:17 回复(0)

python解法

只需要把两个数组合起来排序,再输出中位数即可,所以只需要两行代码:

while True:
    try:

        APlusB=sorted(list(map(int,input().split()[1:]))+list(map(int,input().split()[1:])))
        print(APlusB[len(APlusB)//2] if len(APlusB)%2==1 else APlusB[len(APlusB)//2-1])


    except:
        break

通过测试。

发表于 2017-10-25 15:33:09 回复(0)

问题信息

难度:
2条回答 4348浏览

热门推荐

通过挑战的用户

查看代码
Median