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