首页 > 代码库 > 【Leet Code】Median of Two Sorted Arrays
【Leet Code】Median of Two Sorted Arrays
Median of Two Sorted Arrays
Total Accepted: 17932 Total Submissions: 103927My SubmissionsThere 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)).
Median of Two Sorted Arrays
Total Accepted: 17932 Total Submissions: 103927My SubmissionsThere 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)).
注意这里,There are two sorted arrays(这是两个已经排好序的数组),一看到我就想到了归并排序法,没有使用递归调用,但是任然可以AC:
class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int i = 0, j = 0, k = 0; double r; int* result = new int[m + n]; while( i < m && j < n ) { if( A[i] < B[j] ) { result[k++] = A[i++]; } else { result[k++] = B[j++]; } } while( i < m ) { result[k++] = A[i++]; } while( j < n ) { result[k++] = B[j++]; } if( 1 == (m + n)%2 ) { r = result[(m + n - 1) / 2]; } else { r = (double)( result[(m + n - 2) / 2] + result[(m + n) / 2] ) / 2; } delete [] result; return r; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。