V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
gbin
V2EX  ›  算法

2080324 今日算法

  •  
  •   gbin · 2018-03-24 08:17:38 +08:00 via Android · 3064 次点击
    这是一个创建于 2197 天前的主题,其中的信息可能已经有所发展或是发生改变。
    There are two sorted arrays nums1 and nums2 of size m and n respectively.

    Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

    Example 1:
    nums1 = [1, 3]
    nums2 = [2]

    The median is 2.0
    Example 2:
    nums1 = [1, 2]
    nums2 = [3, 4]

    The median is (2 + 3)/2 = 2.5

    求两个有序数组的中位数。

    PS: Leetcode 004 题
    15 条回复    2018-03-25 09:41:55 +08:00
    pwrliang
        1
    pwrliang  
       2018-03-24 08:54:50 +08:00 via Android
    把两个有序数组接起来,然后用快排的分区函数的找中位数?楼下继续…
    pkookp8
        2
    pkookp8  
       2018-03-24 08:57:51 +08:00 via Android
    这是 leetcode 的题目吗,好像见过。有序数组归并排序。总数除以二得到中位数。区分总数奇偶
    gbin
        3
    gbin  
    OP
       2018-03-24 08:59:35 +08:00 via Android
    @pkookp8 Leetcode 004
    pkookp8
        4
    pkookp8  
       2018-03-24 09:00:20 +08:00 via Android
    @gbin 看了描述就回答了,没看到你的 ps 哈哈
    wingkou
        5
    wingkou  
       2018-03-24 09:00:43 +08:00 via Android
    考研 408 真题哈哈哈
    lhx2008
        6
    lhx2008  
       2018-03-24 09:02:03 +08:00
    应该考的是归并排序了,但是好像直接连接排序也没多慢
    lhx2008
        7
    lhx2008  
       2018-03-24 09:05:16 +08:00
    有序的话,也可以分类讨论下 nums2 是在 num1 的左边、中间还是右边,然后一次拼接上去
    wangt21
        8
    wangt21  
       2018-03-24 09:06:34 +08:00 via Android
    @lhx2008 二分查找哦
    Andiry
        9
    Andiry  
       2018-03-24 09:12:49 +08:00
    显然这题考的不是排序
    lhx2008
        10
    lhx2008  
       2018-03-24 09:18:15 +08:00
    '''java
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int[] nums = new int[length];
    System.arraycopy(nums1,0,nums,0,nums1.length);
    System.arraycopy(nums2,0,nums,nums1.length,nums2.length);
    Arrays.sort(nums);
    if (length % 2 == 0) {
    return ((double)(nums[length/2] + nums[length/2 - 1]))/2;
    } else {
    return nums[length/2];
    }
    }
    }

    '''
    emmm...输入复杂度最优,
    提交了三次,最多可以 beats 85.52% (67 ms)
    lhx2008
        11
    lhx2008  
       2018-03-24 09:43:56 +08:00
    """java
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int[] arr = new int[length];
    int i = 0,j = 0; //nums1,nums2
    for( int k = 0 ; k < length; k ++ ){
    if( i >= nums1.length ){
    arr[k] = nums2[j];
    j ++;
    }
    else if( j >= nums2.length ){
    arr[k] = nums1[i];
    i ++;
    }
    else if(nums1[i] < nums2[j]){
    arr[k] = nums1[i];
    i ++;
    }
    else{
    arr[k] = nums2[j];
    j ++;
    }
    }
    if (length % 2 == 0) {
    return ((double)(arr[length/2] + arr[length/2 - 1]))/2;
    } else {
    return arr[length/2];
    }
    }
    }
    """
    不调系统函数耍流氓的方法,但是其实没有上面那个那么快,提交三次最快也就 68ms, beats 84%
    一个原因是 System.arraycopy 是 jvm 实现的,比赋值快得多,Arrays.sort 也不慢
    在 leetcode 上面也看了很多复杂的答案,但是至少在 leetcode 的测试用例来说,那一点时间复杂度优势相当于没有。当然其他情况不好说,要看什么地方用
    victor97
        12
    victor97  
       2018-03-24 10:27:04 +08:00
    题目都说了要 O(log(m+n))的做法了。排序应该是不行的。
    有个 O(log(n+m))的做法是,在 nums1 二分查找一个数,二分判断其在 nums2 的位置,从而得知合并后它的位置,判断是否是中位数。
    zqqian
        13
    zqqian  
       2018-03-24 10:28:09 +08:00
    如果总长度是奇数
    分别二分 num1 和 num2
    对每个二分数 x 检查
    num1 中小于 x 的数目+num2 中小于 x 的数目 是不是等于总长度的一半

    如果总长度是偶数
    二分 num1
    然后取 num2 中与 num1 中的二分值相邻的两个数。
    分别检查
    pwrliang
        14
    pwrliang  
       2018-03-25 05:56:32 +08:00
    我来实现一下一楼我说的方法吧,首先解决一个数组找中位数的问题
    对于 len % 2 == 0,我们求出数组第 len / 2 大的数和 len / 2 + 1 大的数,再求和除以 2 就是中位数,对于 len % 2 == 1 的情况,直接找 len / 2 + 1 大的数就是中位数。
    至于怎么求第 k 大的数( top 问题),可以用快排的分区函数来实现。https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/



    以下代码通过了 leetcode judege:
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] cpy = new int[nums1.length + nums2.length];
    System.arraycopy(nums1, 0, cpy, 0, nums1.length);
    System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length);
    return findForOne(cpy);
    }

    double findForOne(int[] nums) {
    if (nums.length % 2 == 0) {
    int k1 = getKth(nums, 0, nums.length - 1, nums.length / 2);
    int k2 = getKth(nums, 0, nums.length - 1, nums.length / 2 + 1);
    return (k1 + k2) / 2.0;
    }
    return getKth(nums, 0, nums.length - 1, nums.length / 2 + 1);
    }

    int getKth(int[] nums, int lo, int hi, int k) {

    int ans = Integer.MAX_VALUE;
    if (k > 0 && k <= hi - lo + 1) {
    int pos = partition(nums, lo, hi);
    int len = pos - lo;

    if (len == k - 1)
    ans = nums[pos];
    else if (k - 1 < len)
    ans = getKth(nums, lo, pos - 1, k);
    else
    ans = getKth(nums, pos + 1, hi, k - len - 1);
    }
    return ans;
    }

    int partition(int arr[], int l, int r) {
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
    if (arr[j] <= x) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    }
    }
    int tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
    return i;
    }
    }
    pwrliang
        15
    pwrliang  
       2018-03-25 09:41:55 +08:00   ❤️ 1
    更新一下,上面的 top k 算法我摘自 geekforgeek 的,其实我并没有看懂。下面的找 top k 算法来自《算法 第四版》,这个代码更易读懂,运行时间也比上面的代码更短。

    两个数组拼凑需要 O(m+n),如果是偶数长度,查找两次 top k 需要 O(2*(m+n)),奇数长度 O(m+n),因此时间复杂度在 O(2*(m+n))~O(3*(m+n))之间。
    当然另一种方法是用两个指针指向两个数组当前元素,依次将当前最小的元素写入第三个数组,即合并两个有序数组生成的数组也是有序的。然后再找中位数。

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] cpy = new int[nums1.length + nums2.length];
    System.arraycopy(nums1, 0, cpy, 0, nums1.length);
    System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length);
    return findForOne(cpy);
    }

    double findForOne(int[] nums) {
    if (nums.length % 2 == 0) {
    int k1 = getKth(nums, nums.length / 2 - 1);
    int k2 = getKth(nums, nums.length / 2);
    return (k1 + k2) / 2.0;
    }
    return getKth(nums, nums.length / 2);
    }

    //2 1 3 4 5
    int getKth(int[] nums, int k) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
    int j = partition(nums, lo, hi);
    if (j < k)
    lo = j + 1;
    else if (j > k)
    hi = j - 1;
    else {
    return nums[k];
    }
    }
    return nums[k];
    }

    int partition(int[] nums, int lo, int hi) {
    int pivot = nums[lo];
    int i = lo, j = hi + 1;

    while (true) {
    while (nums[++i] < pivot)
    if (i == hi)
    break;
    while (nums[--j] > pivot)
    if (j == lo)
    break;
    if (i >= j) break;
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
    }
    int tmp = nums[lo];
    nums[lo] = nums[j];
    nums[j] = tmp;
    return j;
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3388 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:36 · PVG 18:36 · LAX 03:36 · JFK 06:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.