amcode
amcode
发布于 3个月前

PHP 版 LeetCode 代码实现——4. Median of Two Sorted Arrays(寻找两个有序数组的中位数)

题目描述

给定两个大小为 m 和 n 的有序数组 nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 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

题解

解法一

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function sortarray($array) {
        if(empty($array)) 
            return;
        $count = count($array);
        for ($i=0; $i<$count; $i++){
            for ($j = $i + 1; $j < $count; $j++){
                $tmp = $array[$i];
                if($array[$i]>$array[$j]){
                    $array[$i] = $array[$j];
                    $array[$j] = $tmp;
                }
            }
        }
        return $array;
    }
    function findMedianSortedArrays($nums1, $nums2) {
        $array = array_merge($nums1,$nums2);
        $array = $this->sortarray($array);
        if(count($array)%2 !==0){
            $k = floor(count($array)/2);
            return $array[$k];
        }else{
            $k = count($array)/2;
            return(($array[$k-1]+$array[$k])/2);
        }
    }

}

解法二

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    public function findMedianSortedArrays($nums1, $nums2)
    {
        $nums1 = array_merge($nums1,$nums2);
        sort($nums1);

        $f = floor(count($nums1)/2);
        if(count($nums1) % 2 == 0){
            return ($nums1[$f] + $nums1[$f-1])/2.0;
        }else{
            return $nums1[$f];
        }
    }
}

>>> PHP 版 LeetCode 代码实现——总目录