我要招人

去企业版

首页 > 试题广场 >

两个有序数组的中位数

[编程题]两个有序数组的中位数

热度指数：25725 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。

示例1

输入

[],[1]

输出

1.00000

算法知识视频讲解

Java

牛客-120抢救中心

思路：

（1）把A，B两个数组复制到同一个数组c

（2）Arrays.sort()方法对c数组排个序。

（3）根据c中的元素个数分步：

如果是偶数个元素，居中的两个数字相加在除2（乘1.0是为了转换成浮点数）；

如果是奇数个元素，直接取中间位置的数（没有求平均值不需要再转换浮点数）。

import java.util.*;

public class Solution {
    public double findMedianSortedArrays (int[] A, int[] B) {
        double result = 0.0;
        int[] c = new int[A.length + B.length];
        System.arraycopy(A, 0, c, 0, A.length);
        System.arraycopy(B, 0, c, A.length, B.length);
        Arrays.sort(c);
        if(c.length%2==0) {
            result = (c[c.length/2-1]+c[c.length/2])*1.0/2;
        } else {
            result = c[c.length/2];
        }
        return result;
    }
}

发表于 2020-07-08 10:25:18 回复(0)

Java

奋斗的龙猫

/**
思路：首先定义一个数组，其长度为n+m，
由于是两个有序数组，那么通过归并排序，从而将新定义的数组有序
然后判断新定义的数组的长度是否为奇偶数，如果是奇数，那么注意将中间的数转换成double型返回即可
否则，将中间两个数相加然后除2.0,注意这里除2.0，因为有可能中间两个数的和小于2，那么如果出的不是2.0，那么得到的结果是0，而不是想要的，并且除以2.0可以避免忘记类型转换（虽然int转double类型不需要强制转换）
*/

import java.util.*;

public class Solution {

/**
*
* @param A int整型一维数组
* @param B int整型一维数组
* @return double浮点型
*/
public double findMedianSortedArrays (int[] A, int[] B) {
int[] arr = new int[A.length + B.length];
double result = 0;//中位数
int j = 0, i = 0, n = 0;//j表示A的下标，i表示B的下标，n表示arr的下标
//当两个数组都没有遍历完的时候，将两个数组分别进行比较，小的先插入到新数组中，从而实现有序
while(j < A.length && i < B.length){
if(A[j] < B[i]){
arr[n++] = A[j++];
}else{
arr[n++] = B[i++];
}
}
//如果A没有遍历完，而B遍历完了，那么将A剩下的元素赋值给arr
while(j<A.length){
arr[n++] = A[j++];
}
//同上面的道理
while(i<B.length){
arr[n++] = B[i++];
}
//判断arr的长度奇偶性，如果是奇数，那么中间的数就是中间数，反之中间的两个数字的和的平均值就是中位数
if(arr.length % 2 == 0){
result = (arr[arr.length /2 ] + arr[arr.length / 2 - 1])/2.0;//注意除的是2.0
}else{
result = arr[arr.length / 2];
}
return result;
}
}

编辑于 2020-06-29 21:10:31 回复(0)

Java

牛客294696814号

我的想法是先合并有序数组A和B，再获取中位数，算法符合时间复杂度。

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int na = A.length-1, nb = B.length-1, i = 0;
        int n = A.length + B.length;
        int[] total = new int[n];
        //归并排序
        while(na>=0 && nb>=0){
            if(A[na]>B[nb]){
                total[i] = A[na];
                na--;
            }else{
                total[i] = B[nb];
                nb--;
            }
            i++;
        }
        //合并剩余数组
        if(na<0){
            for(;nb>=0;nb--){
                total[i++] = B[nb];
            }
        }else{
            for(;na>=0;na--){
                total[i++] = A[na];
            }
        }
        //获取中位数
        int mid = (int)Math.floor(n/2);
        if(n%2 == 0){
            return (float)(total[mid-1]+total[mid])/2;
        }else{
            return (float)total[mid];
        }
    }
}

发表于 2020-04-30 22:31:35 回复(0)

Java

国哥帅过吴彦祖

//本题最简单解法
1.链表分两半
2.逆置后一半
3.依次链接两个链表

public ListNode reverse(ListNode head){ if(head==null){ return null;
        } if(head.next==null){ return head;
        }
        ListNode pre= null;
        ListNode next = null; while (head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
            } return pre;
        } //将链表分成两半  public ListNode half(ListNode head){
        ListNode fast = head;
        ListNode slow = head; while (fast.next!=null&&fast.next.next!=null){
           slow = slow.next;
           fast = fast.next.next;
        }
        ListNode p =slow.next;
        slow.next = null; return p;
    } public void reorderList(ListNode head) { if(head==null){ return ;
        } //两个指针 快慢指针 走到头断开两个链表  ListNode half = this.half(head); //第二个链表逆置  ListNode reverse = reverse(half); //链接这两个链表 head reverse  ListNode p = head;
        ListNode q = reverse;   while (p!=null&&q!=null){
            ListNode a = p.next;
            ListNode b = q.next;
            p.next = q;
            q.next=a;
             p =a;
             q=b;
        }
    }

发表于 2019-12-30 16:15:59 回复(1)

Java

华为诚邀你上车

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length+nums2.length];
        int i1=0,i2=0,i=0;
        while(i<nums.length){
            if(i1>=nums1.length)
                nums[i++] = nums2[i2++];
            else if(i2>=nums2.length)
                nums[i++] = nums1[i1++];
            else{
                if(nums1[i1]>nums2[i2])
                    nums[i++] = nums2[i2++];
                else
                    nums[i++] = nums1[i1++];
            }
        }
        if(nums.length%2==1)
            return nums[(nums.length-1)/2];
        else
            return (nums[nums.length/2]+nums[nums.length/2-1])/2.0;
    }
    
}

发表于 2019-01-02 10:42:47 回复(0)

Java

夏彬

public class Solution {

public double findMedianSortedArrays(int A[], int B[]) {
    int m = A.length;
        int n = B.length;
        int[] temp = new int[m + n];
        if((m + n)%2 == 1) {
            return getMid(A,B,(m + n)/2 + 1);
        }
        else {
            return (getMid(A,B,(m + n)/2)+getMid(A,B,(m+n)/2+1))*0.5;
        }

}
public double getMid(int A[],int B[], int k) {
    int m = A.length;
    int n = B.length;
    if(m > n) {
        return getMid(B,A,k);
    }
    if(m == 0) {
        return B[k - 1 ];
    }
    if(k == 1) {
        return Math.min(A[0], B[0]);
    }

    int pa = Math.min(k/2, m);
    int pb = k - pa;
    if (A[pa - 1] <= B[pb - 1]) {
        int A1[] = new int[m - pa];
        int index = 0;
        for(int i = pa;i <m;i++){
            A1[index] = A[i];
            index ++;
        }

        return getMid(A1,B,pb);
    }
    else {
        int B1[] = new int[n - pb];
        int index = 0;
        for(int i =pb;i <n;i++){
            B1[index] = B[i];
            index ++;
        }
        return getMid(A,B1,pa);
    }

}
}

发表于 2017-10-25 18:43:35 回复(0)

Java

萨仁朝格图（大家去脉脉沟通）

import java.util.*;
public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        ArrayList<Integer> db = new ArrayList<Integer>();
        if(A==null || B == null || A.length+B.length==0)return 0;
        for(int i = 0; i < A.length; i++)db.add(A[i]);
        for(int i = 0; i < B.length; i++)db.add(B[i]);
        Collections.sort(db);
        return db.size()%2==0 ? (db.get(db.size()/2)+db.get(db.size()/2-1))/2.0 : db.get(db.size()/2);
    }
}

发表于 2017-08-22 10:06:42 回复(1)