LeetCode4 Median of Two Sorted Arrays

题目地址:https://leetcode.com/problems/median-of-two-sorted-arrays/

这道题就是求两个有序序列的中位数。这也是2015年4月阿里实习生招人附加题第一题

我用的是归并算法,时间复杂度和空间复杂度都为O(M+N)

class Solution {public:double findMedianSortedArrays(int A[], int m, int B[], int n) {int mid = (m+n)/2 + 1;int *c = new int[mid];int i = 0, j = 0;int k = 0;while(i < m && j < n && k < mid){if(A[i] < B[j])c[k++] = A[i++];elsec[k++] = B[j++];}while(i < m && k < mid)c[k++] = A[i++];while(j < n && k < mid)c[k++] = B[j++];double temp = 0;if((m+n)%2 == 0) temp = (c[k-1]+c[k-2])/2.0;else temp = c[k-1];delete []c;return temp;}};

,人总是珍惜未得到的,而遗忘了所拥有的

LeetCode4 Median of Two Sorted Arrays

相关文章:

你感兴趣的文章:

标签云: