Leetcode207: Median of Two Sorted Arrays

2024-08-28 19:32

本文主要是介绍Leetcode207: 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)).

该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题,原问题也得以解决。

首先假设数组A和B的元素个数都大于k/2,我们比较A[k/2-1]和B[k/2-1]两个元素,这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况:>、<和=。如果A[k/2-1]<B[k/2-1],这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。

当A[k/2-1]>B[k/2-1]时存在类似的结论。

当A[k/2-1]=B[k/2-1]时,我们已经找到了第k小的数,也即这个相等的元素,我们将其记为m。由于在A和B中分别有k/2-1个元素小于m,所以m即是第k小的数。(这里可能有人会有疑问,如果k为奇数,则m不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求k/2,然后利用k-k/2获得另一个数。)

通过上面的分析,我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件:

  • 如果A或者B为空,则直接返回B[k-1]或者A[k-1];
  • 如果k为1,我们只需要返回A[0]和B[0]中的较小值;
  • 如果A[k/2-1]=B[k/2-1],返回其中一个;

最终实现的代码为:

class Solution {
public:double findkmins(vector<int>::iterator a, int m, vector<int>::iterator b, int n, int k){if(m>n)return findkmins(b, n, a, m, k);if(m==0)return b[k-1];if(k==1)return min(*a, *b);int pa = min(k/2, m);int pb = k-pa;if(*(a+pa-1)<*(b+pb-1)){return findkmins(a+pa, m-pa, b, n, k-pa);}else if(*(a+pa-1)>*(b+pb-1)){return findkmins(a, m, b+pb, n-pb, k-pb);}elsereturn *(a+pa-1);}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int total = m+n;vector<int>::iterator a = nums1.begin();vector<int>::iterator b = nums2.begin();if(total & 0x1){return findkmins(a, m, b, n, total/2+1);}elsereturn (findkmins(a, m, b, n, total/2)+findkmins(a, m, b, n, total/2+1))/2;}
};

python代码:

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""merge = []index1 = 0index2 = 0while index1 < len(nums1) and index2 < len(nums2):if nums1[index1]<nums2[index2]:merge.append(nums1[index1])index1 += 1else:merge.append(nums2[index2])index2 += 1while index1 < len(nums1):merge.append(nums1[index1])index1 += 1while index2 < len(nums2):merge.append(nums2[index2])index2 += 1total = len(nums1)+len(nums2)if total & 0x1:return merge[total/2]else:return (merge[total/2-1]+merge[total/2])/2.0


这篇关于Leetcode207: Median of Two Sorted Arrays的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115683

相关文章

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

Java多线程编程模式实战指南:Two-phase Termination模式

文章来源: http://www.infoq.com/cn/articles/java-multithreaded-programming-mode-two-phase-termination?utm_source=infoq&utm_campaign=user_page&utm_medium=link 文章代码地址: https://github.com/Visce

[LeetCode] 583. Delete Operation for Two Strings

题:https://leetcode.com/problems/delete-operation-for-two-strings/description/ 题目 Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in

LeetCode - 33. Search in Rotated Sorted Array

33. Search in Rotated Sorted Array  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个数组,这个数组是由两个有序的数组拼接成的(无重复元素),在这个数组中查找元素k的下标. anal

CodeForces 425C Sereja and Two Sequences

题意: 两组数字a和b  如果a[i]等于b[j]  则可将a[i]和b[j]前所有数字删掉  这种操作花费e体力  得到1元钱  或者一次删掉所有数字  这种操作花费等于曾经删除的所有数字个数  做完后得到所有钱  问 一共s体力 可以得到多少钱 思路: dp+二分 由数据可知最多拿到300元钱  因此可以定义  dp[i][j]表示有i元钱时  b串删除到了j处时  a串删到的位

poj 1849 Two(树形dp求直径)

树的直径:一棵树中两个点间的最长距离。 Description The city consists of intersections and streets that connect them.  Heavy snow covered the city so the mayor Milan gave to the winter-service a list of streets that ha

Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example,Given s = “eceba”, T is "ece" which its length is 3. 思路:同向双指针,跟Longest Substrin

Two to One——C语言提高题【7 kyu】

一、原题 链接:Training on Two to One | Codewars Take 2 strings s1 and s2 including only letters from a to z. Return a new sorted string (alphabetical ascending), the longest possible, containing distinct

JavaScript - First step - Arrays

创建数组 任何类型的对象,都可以放入数组中。 var shopping = ['bread', 'milk', 'cheese', 'hummus', 'noodles'];shopping;// (5) ["bread", "milk", "cheese", "hummus", "noodles"]var sequence = [1, 1, 2, 3, 5, 8, 13];var ra

LeetCode --- Median of Two Sorted Arrays

第一次在csdn上写备忘录,以前一直是在笔记本上写,主要是笔记本上可以随意写,只要自己能看懂,在网页上多少都受些限制,另外一方面也是想锻炼下写作能力,为以后的论文做基础吧!最近偶尔上leetcode练些题目,所以也就以这个为主题写一篇试试看,因为能力不足,理解或言辞上会有错误,还望访者不吝赐教,我定当万分感激。 好了,废话也说完了,现在进入正题: 题目: There are two sor