首页 > 代码库 > 【LeetCode】Median of Two Sorted Arrays (2 solutions)
【LeetCode】Median of Two Sorted Arrays (2 solutions)
Median of Two Sorted Arrays
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)).
解法一：保底做法，O(m+n)复杂度
按照归并排序的思路，数到median，然后计算返回。
需要注意：
如果是m+n是偶数，需要返回两个中位数的均值
class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { if(m==0 && n==0) return 0; else if(m==0 && n!=0) return ((double)(B[(n-1)/2]+B[n/2]))/2; else if(m!=0 && n==0) return ((double)(A[(m-1)/2]+A[m/2]))/2; //m!=0 && n!=0 int total = m+n; bool isEven = (total%2==0)?true:false; int ind = (total-1)/2; int i = 0; int j = 0; int tag = false; //false--no candidate; true--one candidate int ret1; int ret2; while(i<m && j<n) { if(ind==0 && tag==false) { ret1 = min(A[i],B[j]); tag = true; if(!isEven) return ret1; } else if(ind==-1 && tag==true) { ret2 = min(A[i],B[j]); return ((double)(ret1+ret2))/2; } if(A[i] <= B[j]) i ++; else j ++; ind --; } while(i<m) { if(ind==0 && tag==false) { if(!isEven) return A[i]; else return ((double)(A[i]+A[i+1]))/2; } else if(ind==-1 && tag==true) { ret2 = A[i]; return ((double)(ret1+ret2))/2; } i ++; ind --; } while(j<n) { if(ind==0 && tag==false) { if(!isEven) return B[j]; else return ((double)(B[j]+B[j+1]))/2; } else if(ind==-1 && tag==true) { ret2 = B[j]; return ((double)(ret1+ret2))/2; } j ++; ind --; } }};
【LeetCode】Median of Two Sorted Arrays (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。