LeetCode4—寻找两个正序数组的中位数

顺序表 查找

第一次提交的代码：(归并排序）

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int[] num=new int[3000];
      int head1,head2,head,m=nums1.length,n=nums2.length;//求数组长度：.length就可，不要括号！！！
      head1=head2=head=0;
      while(head1<m&&head2<n)
      {
        if(nums1[head1]>nums2[head2]) 
        {
            num[head]=nums2[head2];
            head++;
            head2++;
        }
        else
        {
            num[head]=nums1[head1];
            head++;
            head1++;
        }
      }
      while(head1<m)
      {
         num[head]=nums1[head1];
         head++;
         head1++;
      }
      while(head2<n)
      {
         num[head]=nums2[head2];
         head++;
         head2++;
      }
      int t=(n+m)/2;
      return ((n+m)%2==1)?num[t]:((num[t-1]+num[t])/2.0); //注意想的是第n个数，写的编号是n-1
    }
}

第二次提交的代码：（归并排序+常数优化）

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int head1,head2,head,m=nums1.length,n=nums2.length,t,Now=0,Las=0;
      head1=head2=head=0;
      t=(n+m)/2;
      boolean tag=((n+m)%2==1);
      while(head1<m&&head2<n)
      {
        if(nums1[head1]>nums2[head2]) 
        {
            Las=Now;Now=nums2[head2];
            if(head==t) return tag?Now:((Now+Las)/2.0);
            head++;head2++;
        }
        else
        {
            Las=Now;Now=nums1[head1];
            if(head==t) return tag?Now:((Now+Las)/2.0);
            head++;head1++;            
        }
      }
      while(head1<m)
      {
         Las=Now;Now=nums1[head1];
         if(head==t) return tag?Now:((Now+Las)/2.0);
         head++;head1++;
      }
      while(head2<n)
      {
         Las=Now;Now=nums2[head2];
         if(head==t) return tag?Now:((Now+Las)/2.0);
         head++;head2++;
      }
      return -1;
    }
}

第三次提交的代码：（二分查找）

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      if(nums1.length>nums2.length)
      {
          int[] tmp=nums1;
          nums1=nums2;
          nums2=tmp;//用小数组二分，减小二分范围
      }
      int m=nums1.length,n=nums2.length;
      int tot=(n+m+1)/2;
      int L=0,R=m;//二分nums1出了多少个数，结果为L
      while(L<R)
      {
          int mid=(L+R+1)/2,j=tot-mid;//二分注意：不加1的话会在R-L=1时出死循环
          if(nums1[mid-1]<=nums2[j]) L=mid;
          else R=mid-1;
      }
      int i=L,j=tot-i;
      int s1L=(i==0)?Integer.MIN_VALUE:nums1[i-1],
          s1R=(i==m)?Integer.MAX_VALUE:nums1[i],
          s2L=(j==0)?Integer.MIN_VALUE:nums2[j-1],
          s2R=(j==n)?Integer.MAX_VALUE:nums2[j];//特殊处理分割线恰好在数组边界的情况
      if((n+m)%2==1) return Math.max(s1L,s2L);
      else return (Math.max(s1L,s2L)+Math.min(s1R,s2R))/2.0;
    }
}