编程题：在两个长度相等的排序数组中找到上中位数
在两个长度相等的排序数组中找到上中位数
http://www.nowcoder.com/questionTerminal/08588d568e164e0a9958b5d6a3c351f5
链接：传送门
来源：牛客网
问题描述：
解题思路：
思路1：暴力解法
观察题我们可以得到：就是有两个有序的数组，然后把他们合并起来时求出这一串数据的中位数。
既然是求新组合数据的中位数，那么我们可以将这两个数组合并为一个数组，然后重新排序，找出要求的中位数就好了。
思路2：思路1的改装版
同样是将这两个数组合并为一个数组，然后重新排序的思路（思路1是全部数据放进去排序，这里我们可以实现进行排序然后在放进新数组），这样我们就可以不用快排的递归：
- arr1[0]和arr2[0]比较，选出较小的放在新数组的arr[0]。
- 假如上边是arr1[0]>arr2[0],将arr2[0]赋值到arr[0]后，我们将进行arr1[0]和arr2[1]的比较，再次选出小的放进新数组中。
- 如此循环2步骤，肯定会有一个数组会先遍历完，然后我们将另一个数组未遍历的元素放进新数组就好了。
- 这样新数组的所有数据在放进后就是有序的，我们直接选中位数返回即可。
思路3：递归版
题上说两个数组事先就是有序的，那个请往下看：
举例1，比如两个数组是这样的：
当两个数组的长度为偶数时：
分别选出这两个数组的上中位数的下标，即
mid1 = (n-1)/2 = 1
mid2 = (n - 1)/2 = 1
- 假如 arr2[mid2] > arr1[mid1]，那么我们要找的目标数是一定存在于 arr1[mid1+1…n] 和 arr2[0…mid2]中，而不可能存在于 arr1[0…mid1] 和 arr2[mid2+1…n] 之中，也就是说，我们接下来只需要在arr1[mid1+1…n] 和 arr2[0…mid2] 中查找就行了。
举例2，比如两个数组是这样的：
当两个数组的长度为奇数时：
分别选出这两个数组的上中位数的下标，即
mid1 = (n-1)/2 = 2
mid2 = (n - 1)/2 = 2
- 这个时候如果 arr2[mid2] > arr1[mid1] 时，则和上面那个情况有点小差别，这时候目标数只存在于 arr1[mid1…n] 和 arr2[0…mid2]中。
- 注意他们的差别，从arr1[mid1+1…n] => arr1[mid1…n]。
思路4：思路3的改装，迭代版
理解了思路3的原理后，由于递归会不停的调用栈（直到出口），所以我们可以将其代码改编为迭代版的。
解题代码：
思路1代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
//开辟一个新数组来存放以前两个数组的数据，数组大小是他两之和
int[] arr=new int[2*n];
int[] arr1=new int[n];
int[] arr2=new int[n];
int j=0;
for(int i=0;i<arr1.length;i++){
arr1[i]=sc.nextInt();
//在输入arr1数据的同时对arr的数组也进行赋值
arr[j]=arr1[i];
j++;
}
for(int i=0;i<arr2.length;i++){
arr2[i]=sc.nextInt();
//在输入arr2数据的同时对arr的数组也进行赋值
arr[j]=arr2[i];
j++;
}
quickSort(arr); //开始快速排序
//题上说要求的是具体的数，这里我们是根据它的下标返回的
if(arr.length%2==0){
System.out.println(arr[n-1]); //本来是n,下标要减1，所以是n-1
}else{
System.out.println(arr[n/2]);//本来是n/2+1,下标要减1，所以是n/2
}
}
}
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
public static void quick(int[] arr,int low,int high){
if(low==high){
return;
}
int par=partion(arr,low,high);
if(par>low+1){
quick(arr,low,par-1);
}
if(par+1<high){
quick(arr,par+1,high);
}
}
public static int partion(int[] arr,int low,int high){
int temp=arr[low];
while(low<high){
while((low<high)&&arr[high]>=temp){
high--;
}
if(low==high){
break;
}else{
arr[low]=arr[high];
}
while((low<high)&&arr[low]<=temp){
low++;
}
if(low==high){
break;
}else{
arr[high]=arr[low];
}
}
arr[low]=temp;
return low;
}
} 思路2代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] arr=new int[2*n];
int[] arr1=new int[n];
int[] arr2=new int[n];
for(int i=0;i<arr1.length;i++){
arr1[i]=sc.nextInt();
}
for(int i=0;i<arr2.length;i++){
arr2[i]=sc.nextInt();
}
int x=0; //arr的指针（这样就知道新***来的元素往哪放）
int j=0;//对arr1遍历的指针
int p=0;//对arr2遍历的指针
while(j<n&&p<n){ //循环的出口是任意一个数组遍历完
if(arr1[j]<=arr2[p]){
//小的放进新数组后继续小的元素的下一个元素和刚刚较大的对比
arr[x]=arr1[j];
j++;
}else{
arr[x]=arr2[p];
p++;
}
x++; //放进新数组一个元素后，下次放到插入元素的后边
}
if(j==n){ //说明arr2没有遍历完
for(;x<arr.length;x++){
arr[x]=arr2[p++]; //把arr2剩下的元素搬到新数组中
}
}
if(p==n){ //同上
for(;x<arr.length;x++){
arr[x]=arr2[j++];
}
}
//按照题上的要求进行返回
if(arr.length%2==0){
System.out.println(arr[n-1]);
}else{
System.out.println(arr[n/2]);
}
}
}
} 思路3代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] arr1=new int[n];
int[] arr2=new int[n];
for(int i=0;i<arr1.length;i++){
arr1[i]=sc.nextInt();
}
for(int i=0;i<arr2.length;i++){
arr2[i]=sc.nextInt();
}
System.out.println(getUpMedian(arr1,arr2));
}
}
private static int getUpMedian(int[] arr1,int[] arr2){
//开始寻找
return find(arr1,0,arr1.length-1,arr2,0,arr2.length-1);
}
//l1代表下一次在arr1寻找的起始下标，r1是终止下标
//l2,r2同上
private static int find(int[] arr1,int l1,int r1,int[] arr2,int l2,int r2){
//计算得出每次的mid1,mid2，计算的时候前边加的l1,l2是加上相比上一次下标的的偏移量
int mid1=l1+(r1-l1)/2;
int mid2=l2+(r2-l2)/2;
//当数组中只剩一个数的时候，把两个数组中较小的数返回
//假如arr1={1},arr2={2};排序后是1 2，我们应该返回1
if(l1>=r1||l2>=r2){
return Math.min(arr1[l1],arr2[l2]);
}
//元素个数为奇数时，offset(偏移量)为0；为偶数时offset为1
int offset=((r1-l1+1)&1)^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{ //arr1[mid1]==arr2[mid2]
return arr1[mid1];// 返回 arr2[mid2]也可以
}
}
} 思路4代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] arr1=new int[n];
int[] arr2=new int[n];
for(int i=0;i<arr1.length;i++){
arr1[i]=sc.nextInt();
}
for(int i=0;i<arr2.length;i++){
arr2[i]=sc.nextInt();
}
System.out.println(getUpMedian2(arr1,arr2));
}
}
private static int getUpMedian2(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&&l2<r2){
mid1=l1+(r1-l1)/2;
mid2=l2+(r2-l2)/2;
offset=((r1-l1+1)&1)^1;
if (arr1[mid1] < arr2[mid2]) {
l1=mid1+offset;
r2=mid2;
} else if (arr1[mid1] > arr2[mid2]) {
r1=mid1;
l2=mid2+offset;
} else {
return arr1[mid1];// 返回 arr2[mid2]也可以
}
}
return Math.min(arr1[l1],arr2[l2]);
}
}
投递京东等公司10个岗位 >