Leetcode 算法 -4. Median of Two Sorted Arrays

Leetcode 算法 -4. Median of Two Sorted Arrays

Posted August 17, 2016

问题链接: 4. Median of Two Sorted Arrays 问题描述: There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Python

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

Python

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

使用语言: Python

解题思路: 先把列表碾平 , 由于两个列表元素类型相同直接相加即可. 然后排序. 计算中间位置, 可以通过判断奇偶数来分别处理开始index和结束index. 如果长度为奇数则直接返回最中间的, 如果为偶数则返回一个长度为2的list. 计算后返回. 注意: 计算要使用float类型.

Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = sorted(nums1 + nums2)
        if len(nums) % 2:
            s = len(nums) / 2
        else:
            s = len(nums) / 2 - 1

        e = len(nums) / 2 + 1

        rs = nums[s:e]
        if len(rs) == 1:
            return rs[0]
        else:
            return sum(rs) / float(2)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏恰童鞋骚年

剑指Offer面试题:14.链表的倒数第k个节点

PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善。

1074
来自专栏noteless

[十一]基础数据类型之Character

该类提供了几种方法来确定字符的类别(小写字母、数字等),并将字符从大写转换为小写,反之亦然

851
来自专栏PHP在线

开发中遇到一个数据库字段问题

大牛不必浪费时间了,适合初学者。 今天遇到一个问题,数据库字段问题。 有一张表存储着用户消费记录,设计表时使用的是整形,后来增加需求,需要对业务做些改动,改过之...

3386
来自专栏星汉技术

HIVE内置函数

6896
来自专栏chenjx85的技术专栏

leetcode-49-字母异位词分组(神奇的哈希)

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

841
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(2)--《Java数据结构和算法》第二版 Robert lafore第二章【数组】编码作业

2103
来自专栏伪君子的梦呓

题解~按照特定的格式输出~C++做法

一共三行,第一行:位数 第二行: 用空格分开的每个数字,注意最后一个数字后没有空格 第三行: 按逆序输出这个数

544
来自专栏Jackson0714

C# 正则表达式

1172
来自专栏blackheart的专栏

[C#1] 8-数组

1.数组概述 声明数组: //每个元素初始化为0,虽然数组元素是值类型,但是却是分配在托管堆中的; int[] myArray=new int[100]; //...

1927
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-双向链表类定义《数据结构与算法分析》

将新的节点插入双向链表的时候: iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点 { ...

2226

扫码关注云+社区

领取腾讯云代金券