leetcode 4. 寻找两个正序数组的中位数

问题其实可以转化成寻找两个有序数组中的第 k小的数,可用折半删除法求解。

题干

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

 

示例1

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

则中位数是 2.0

 

示例2

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

则中位数是 (2 + 3)/2 = 2.5

 

实现

PHP

此解法是使用数组合并后重新排序,没有利用起两个数组有序的这个条件,时间复杂度并不符合题目要求。(但胜在能快速解决问题)

执行用时:44 ms, 在所有 PHP 提交中击败了40.30%的用户
内存消耗:15.1 MB, 在所有 PHP 提交中击败了100.00%的用户
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {

        $arr = array_merge($nums1, $nums2);
        sort($arr);

        $length=count($arr);
        if($length%2==1){
            //取中间的数
            $index=intval($length/2);
            return $arr[$index];
        }else{
            //求中间两位数的平均值
            $index1= $length/2;
            $index2=($length/2)-1;
            return ($arr[$index1]+$arr[$index2])/2;
        }
    }
}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇