首页 > 代码库 > leetcode 2.Median of Two Sorted Arrays
leetcode 2.Median of Two Sorted Arrays
Median of Two Sorted Arrays Problem:
There are two sorted arrays A and B 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)).
解题思路：如果是一个已排序数组，求中位数，可以直接计算。因此比较常规的想法是直接将两个有序数组合并，类型归并排序的一次merge过程。
class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int *X = new int[m + n]; int i = 0, j = 0, k = 0; double median; while ((i < m) && (j < n)) { if (A[i] <= B[j]) X[k++] = A[i++]; else X[k++] = B[j++]; } while (i < m) X[k++] = A[i++]; while (j < n) X[k++] = B[j++]; if (k & 1) median = X[(k + 1)/2 - 1]; else median = (X[k/2 - 1] + X[k/2])/(double)2; delete []X; return median; }};
leetcode 2.Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。