欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在两个长度相等的排序数组中找到中位数

程序员文章站 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]);
}
相关标签: 算法学习