`
standalone
  • 浏览: 609716 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

[leetcode] find median of two sorted arrays

 
阅读更多
http://leetcode.com/onlinejudge#question_4



Solution: a little ugly.

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int len1 = A.length;
        int len2 = B.length;
        int i = 0; 
        int j = 0;
        int k = 0;
        double v = 0;
        double pre = 0;
        
        boolean odd = (len1 + len2) % 2 == 1;
        int mid = (len1 + len2) / 2 + 1;
                
        while(i<len1 && j<len2 && k < mid){
            if(A[i] < B[j]) { 
                v = A[i];
                if(k == mid-2){
                    pre = A[i];
                }                
                i++;
            }
            else {
                v = B[j];
                if(k == mid-2){
                    pre = B[j];
                }
                j++;                
            }            
            k++;            
        }
        if(k==mid){
            if(odd){
                return v;
            }else {
                return (double)(v + pre)/2;
            }
        }
        
        while(i<len1 && k < mid){
            v = A[i];
            if(k==mid-2) pre = A[i];
            i++;
            k++;            
        }
        if(k==mid){
            if(odd){
                return v;
            }else {
                return (double)(v + pre)/2;
            }
        }
        
        while(j<len2 && k<mid){
            
            v = B[j];
            if(k==mid-2) pre = B[j];
            j++;
            k++;
        }
        if(k==mid){
            if(odd){
                return v;
            }else {
                return (double)(v + pre)/2;
            }
        }
        return v;
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics