4.两个排序数组的中位数

超、凢脫俗 2021-09-16 17:06 297阅读 0赞

# 4.两个排序数组的中位数 #

*  题目描述：  
    给定两个大小为 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

将两个数组合并，然后从中找取合并数组中的中位数即可，代码如下：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    	      int[] array = new int[nums1.length+nums2.length];	//合并数组
    	      System.arraycopy(nums1, 0, array, 0, nums1.length);	//将数组复制到合并数组中
    	      System.arraycopy(nums2, 0,array, nums1.length,nums2.length);  //将数组复制到合并数组中
    	      Arrays.sort(array);	//对数组进行排序
    	      if(array.length%2!=0) {	//查找中位数
    	    	  return array[array.length/2];
    	      }
    	      else
    	      {
    	    	  return (array[array.length/2]+array[array.length/2-1])/2.0;	//查找中位数
    	      }
    	}

分析上面的代码我们可知,将两个数组复制到新数组的时间复杂度分别为O(m)、O(n)，排序的时间复杂度O((n+m)log(n+m))、返回值只需O(1)，最后的时间复杂度为O((n+m)log(n+m))，并且用了O(n+m)的辅助空间。

发表评论取消回复

表情：

评论列表（有 0 条评论，297人围观）

还没有评论，来说两句吧...

相关阅读

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

> 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 > > 示例 1： > > 输入：num

我会带着你远行/ 2022年10月10日 12:56/ 0 赞/ 151 阅读

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

[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/][https_leetcode-cn.com_pr

快来打我*/ 2022年09月08日 03:56/ 0 赞/ 210 阅读

相关 LeetCode-4. 两个排序数组的中位数

4. 两个排序数组的中位数 [题目描述][Link 1] -------------------- 给定两个大小为 m 和 n 的有序数组 nums1 和 nu

淩亂°似流年/ 2022年05月26日 11:30/ 0 赞/ 158 阅读

相关 LeetCode刷题笔记(四）两个排序数组的中位数

题目：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。示例1：

痛定思痛。/ 2022年05月26日 04:26/ 0 赞/ 149 阅读

相关 LeetCode第四题之两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。示例 1:

阳光穿透心脏的1/2处/ 2022年05月25日 23:20/ 0 赞/ 155 阅读

相关【算法题】两个排序数组的中位数

问题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。示例

喜欢ヅ旅行/ 2022年05月25日 07:58/ 0 赞/ 157 阅读

相关 4. 两个排序数组的中位数

[题目描述][Link 1] [提示帮助][Link 2] [提交记录][Link 3] 社区讨论 [阅读解答][Link 4] [随机一题][Link 5] ------

￡神魔★判官ぃ/ 2022年05月21日 09:20/ 0 赞/ 160 阅读

相关 Leetcode No.4 两个排序数组的中位数/Median of Two Sorted Arrays

问题描述：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

分手后的思念是犯贱/ 2022年05月17日 05:21/ 0 赞/ 169 阅读

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

package com.cheng.leetcode; import java.util.ArrayList; import java.uti

- 日理万妓/ 2021年09月21日 14:30/ 0 赞/ 294 阅读

相关 4.两个排序数组的中位数

4.两个排序数组的中位数题目描述：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。

超、凢脫俗/ 2021年09月16日 17:06/ 0 赞/ 298 阅读