在两个长度相等的排序数组中找到中位数
程序员文章站
2024-03-15 22:00:30
...
/*public class Main{
public static int getUpMedia(int[] arr1,int[] arr2) {
if(arr1 == null || arr2 == null) {
return -1;
}
else {
return find(arr1,0,arr1.length-1,arr2,0,arr2.length-1);
}
}
public static int find(int[] arr1,int l1,int r1,int[] arr2,int l2,int r2) {
int mid1 = l1 + (r1 - l1) / 2;
int mid2 = l2 + (r2 - l2) / 2;
if(l1 >= r1) {
return Math.min(arr1[l1], arr2[l2]);
}
//元素个数为奇数,则offset=0,反之为1
int len = r1 - l1 +1;
int offset = 0;
if(len % 2 == 0) {
offset = 1;
}
if(arr1[mid1] < arr2[mid2]) {
return find(arr1,mid1+offset,r1,arr2,l2,mid2);
}else if(arr1[mid1] > arr2[mid2]){
return find(arr1,l1,mid1,arr2,mid2+offset,r2);
}else {
return arr1[mid1];
}
}
public static void main(String[] args) {
}
}*/
public static int getUpMedia(int[] arr1,int[] arr2) {
if(arr1 == null || arr2 == null) {
return -1;
}
int l1 = 0;
int r1 = arr1.length - 1;
int l2 = 0;
int r2 = arr2.length - 1;
int mid1 = 0;
int mid2 = 0;
int offset = 0;
while(l1 < r1) {
mid1 = l1 + (r1 - l1) / 2;
mid2 = l2 + (r2 - l2) / 2;
int len = r1 - l1 + 1;
if(len % 2 == 0) {
offset = 1;
}
if(arr1[mid1] < arr2[mid2]) {
l1 = mid1 + offset;
r2 = mid2;
}else if(arr1[min1] > arr2[mid2]) {
r1 = mid1;
l2 = mid2 + offset;
}else {
return arr2[mid1];
}
}
return Math.min(arr1[l1],arr2[l2]);
}
上一篇: topK问题——N个数中取最大的K个数