/***4.求两个正序数组的中位数*给定两个大小分别为m和n（从小到大）的正序数组nums1和nums2。请找到并返回这两个有序数组的中位数。**算法的时间复杂度应为O(log(m+n))**/publicclassMedian{publicstaticdoublefindMedianElement(int[]numArray1,int[]numArray2){intlength1=numArray1.length,length2=numArray2.length;inttotalLength=length1+length2;//奇数if(totalLength%2==1){intmidIndex=totalLength/2;双中位数=getElement(numArray1,numArray2,midIndex+1);返回中位数；}else{//偶数intmidIndex1=totalLength/2-1,midIndex2=totalLength/2;intk1=getElement(numArray1,numArray2,midIndex1+1);intk2=getElement(numArray1,numArray2,midIndex2+1);双中位数=(k1+k2)/2.0;返回中位数；}}publicstaticintgetElement(int[]numArray1,int[]numArray2,intk){intlength1=numArray1.length,length2=numArray2.length;int索引1=0,索引2=0;//临时存储KintkTemp=k;//记录遍历次数intcount=0;while(true){//特殊情况，取第一个元素if(k==1){if(length1==0){returnnumArray2[index2];}if(length2==0){返回numArray1[index1];}返回Math.min(numArray1[index1],numArray2[index2]);}//元素初值intpivot1=-99999,pivot2=-99999;//数组1，下标不越界，数组个数大于0if(index1<=length1-1&&length1>0){pivot1=numArray1[index1];}//数组2，下标不越界，且数组个数大于0if(index2<=length2-1&&length2>0){pivot2=numArray2[index2];}//已经遍历了k-1次就相当于找到了目标元素if(count==(kTemp-1)){if(index1>length1-1){returnpivot2;}如果(index2>length2-1){returnpivot1;}返回Math.min(pivot1,pivot2);}//谁的元素小谁移动指针if((pivot1!=-99999&&pivot2!=-99999&&pivot1<=pivot2)||pivot2==-99999){//右移nums1指针index1+=1;//记录遍历次数count+=1;}else{//右移nums2指针index2+=1;//记录遍历次数count+=1;}}}
