LeetCode #4 Median of Two Sorted Arrays

2019-11-06 06:48:36

字体：大中小

来源：转载

供稿：网友

Description

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

nums1 = [1, 3] nums2 = [2] The median is 2.0

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

Analysis

题目难度为：hard 起初以为这道题并不难，但是开始着手做了之后才发现了这道的复杂性。首先看题目要求，对于时间复杂度的要求是O（log(m+n)），那么首先想到的方法必然是二分法，或者近似二分法的方法。我们需要找到中点，那么也就是说，我们需要找到第（m+n）/2大的数；也就是说，要有（m+n）/2-1个数比中位数小，取两个数组的第（m+n）/4来进行比较；分成三种情况：1、a>b，说明b的前面（m+n）/4个数一定小于中位数，可以排除；2、a

Code（c )

int min (int a, int b) { if (a > b) return b; else return a;}double findKth(int *a, int m, int *b, int n, int k) { if (m > n) return findKth(b, n, a, m, k); if (m == 0) if () return b[k - 1]; if (k == 1) return min(a[0], b[0]); //divide k into two parts int pa = min(k / 2, m), pb = k - pa; if (a[pa - 1] < b[pb - 1]) return findKth(a + pa, m - pa, b, n, k - pa); else if (a[pa - 1] > b[pb - 1]) return findKth(a, m, b + pb, n - pb, k - pb); else return a[pa - 1]; } double findMedianSortedArrays(int *A, int m, int *B, int n) { int total = m + n; if (total & 0x1) { return findKth(A, m, B, n, total / 2 + 1); } else { return ((findKth(A, m, B, n, total / 2) + findKth(A, m, B, n, total / 2 + 1))/2; }}

上一篇：POJ1308 Is It A Tree?(树，并查集)

下一篇：sublime 安装phpcs

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注