当前位置: 首页 > news >正文

Median of Two Sorted Arrays

每日算法——letcode系列


问题 Median of Two Sorted Arrays

Difficulty: Hard

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)).

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
    }
};

翻译

两个有序数组的中位数

难度系数:困难

有两个大小分别为m和n的 nums1nums2有序数组。 找出这两个有序数组的中位数。 时间复杂度应为$O(log (m+n))$.

思路

先转化成topK问题,再分两种情况:

  • m + n为奇数时,返回第K就好

  • m + n为偶数时,返回第K和K + 1的平均值

由于题目要求是O(log(m+n))时间复杂度,那必须得用有序的信息,想到二分法,总想把两数组各减一半最好,但这种可能把中位数也剔除了,
如:
[1, 2, 5, 6] -> [5, 6]

 [3, 4, 7, 8] -> [7, 8] 这样就把中位数4给剔除了,但可以得用一点,上面个数组中的[1, 2]是可以剔除的。

两长度分别为m, n的数组A, B,假设k = $\frac{(m + n) }{2}$ 。
将k分成两成pa,pb两部分,由于是两个数组,长度不一致,为不越界,有两种分法:(假设m>n)

  • 当$\frac{k}{2}$ $\leq$n时, 直接分成pa = pa = $\frac{k}{2}$

  • 当$\frac{k}{2}$ > n时, pa = n, pb = k - pa

下面分析当$\frac{k}{2}$ $\leq$n的三种情况

  1. A[$\frac{k}{2}$] == B[$\frac{k}{2}$]

  2. A[$\frac{k}{2}$] > B[$\frac{k}{2}$]

  3. A[$\frac{k}{2}$] < B[$\frac{k}{2}$]

  • 第一种情况:
    如果将B合并到A,那么B[0]到B[$\frac{k}{2}$-1]肯定在A的左边, B[$\frac{k}{2}$+1]到B[n]肯定放在A的右边,那中位数即为A[$\frac{k}{2}$]、B[$\frac{k}{2}$]

  • 第二种情况:
    如果:中位数在B[0]到B[$\frac{k}{2}$]中, 假设中位数的索引为mid。

那么B[0] $\leq$B[mid] $\leq$B[$\frac{k}{2}$], 则B中至少有n - $\frac{k}{2}$个在B[mid] 右边
由于A[$\frac{k}{2}$] > B[$\frac{k}{2}$], 则A中至少有m - $\frac{k}{2}$ + 1个在B[mid] 右边
则至少有n - $\frac{k}{2}$ + m - $\frac{k}{2}$ + 1 = k + 1个数在B[mid]的右边, 则当且仅当mid = $\frac{k}{2}$满足要求, 比如A = [6], B = [1, 2, 8],如果A[$\frac{k}{2}$ -1] > B[$\frac{k}{2}$ -1]呢?
同上分析得:则至少有n - ($\frac{k}{2}$ -1) + m - ($\frac{k}{2}$-1) + 1 = k + 3> k+1个数在B[mid]的右边, 则中位数肯定不在B[0]到B[$\frac{k}{2}$ -1]中,可剔除

  • 第三种情况同第二种类似:当A[$\frac{k}{2}$ -1] < B[$\frac{k}{2}$ -1]中位数肯定不在A[0]到A[$\frac{k}{2}$ -1]中。

由上分析可得:

  1. A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1时:A[$\frac{k}{2}$-1]、 B[$\frac{k}{2}$-1]为中位数

  2. A[$\frac{k}{2}$-1] > B[$\frac{k}{2}$-1]时:中位数肯定不在B[0]到B[$\frac{k}{2}$-1]中

  3. A[$\frac{k}{2}$-1] < B[$\frac{k}{2}$-1]时:中位数肯定不在A[0]到A[$\frac{k}{2}$-1]中

则我们可以递归的剔除二个数组中的一些数

中止条件:

  • 当A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1时,返回其中一个

  • 当A、B中一个为空时, 分别返回B[k-1]或A[k-1]

  • 当k = 1时, 返回A[0]、B[0]中小的一个

当$\frac{k}{2}$ > n时, 也是同样的分析方法

代码


//
//  main.cpp
//  Median of Two Sorted Arrays
//
//  Created by zhz on 15/12/15.
//  Copyright (c) 2015年 zhz. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = static_cast<int>(nums1.size());
        int n = static_cast<int>(nums2.size());
        int k = (m + n + 1) / 2;
        
        if ((m + n) % 2 != 0){
            return findKthBigNum(nums1, nums2, k);
        }
        else{
            return  (findKthBigNum(nums1, nums2, k + 1) + findKthBigNum(nums1, nums2, k)) / 2.0;
        }
        
    }
    
private:
    double findKthBigNum(vector<int>& nums1, vector<int>& nums2, int k){
        int m = static_cast<int>(nums1.size());
        int n = static_cast<int>(nums2.size());
        if (n > m){
            return findKthBigNum(nums2, nums1, k);
        }
        if (n == 0){
            return nums1[k - 1];
        }
        if (k == 1){
            
            return nums1[0] < nums2[0] ? nums1[0] : nums2[0];
        }
        
        int pa = min(k / 2, n), pb = k - pa;
        
        if (nums1[pb - 1] == nums2[pa - 1]){
            
            return nums2[pa - 1];
        }
        else if (nums1[pb - 1] > nums2[pa - 1])
        {
            vector<int> tempNums;
            if (pa <= nums2.size()){
                tempNums.assign(nums2.begin() + pa, nums2.end());
                 k = k - pa;
            }
            else{
                k = k - static_cast<int>(nums2.size());
            }
            return findKthBigNum(nums1, tempNums, k);
        }
        else
        {
            vector<int> tempNums;
            if (pb <= nums1.size()){
                tempNums.assign(nums1.begin() + pb, nums1.end());
                k = k - pb;
            }
            else{
                k = k - static_cast<int>(nums1.size());
            }
           
            return findKthBigNum(tempNums, nums2, k);
        }
    }
};
int main(int argc, const char * argv[]) {
    vector<int> nums1 = {3};
    vector<int> nums2 = {1, 2, 4};
    
    auto s = new Solution();
    double mid = s->findMedianSortedArrays(nums1, nums2);
    std::cout << "Hello, World!\n";
    return 0;
}

后记: 代码的实现有很多细节活,一定要多练,不能光靠想

相关文章:

  • 固态硬盘上安装Windows8(ghost)启动问题
  • 王家林每日大数据语录Spark篇0003
  • [hive小技巧]同一份数据多种处理
  • 【191】◀▶ Powershell 命令集 Cmdlets
  • Github访问慢解决办法
  • ActionContext 中的数据详解
  • SpringMVC格式总结
  • QT内使用OpenCV
  • FRC与tableview的联合使用
  • Sublime Text 3安装与使用
  • 解放全天下开发者
  • Cesium 获取当前视图范围
  • Gradle介绍
  • 扩展SpringMVC以支持绑定JSON格式的请求参数
  • 0x05 Python数据分析,Anaconda八斩刀
  • CentOS从零开始部署Nodejs项目
  • CSS 三角实现
  • DataBase in Android
  • ES学习笔记(12)--Symbol
  • FastReport在线报表设计器工作原理
  • in typeof instanceof ===这些运算符有什么作用
  • Java知识点总结(JDBC-连接步骤及CRUD)
  • PHP的类修饰符与访问修饰符
  • Protobuf3语言指南
  • thinkphp5.1 easywechat4 微信第三方开放平台
  • vue从创建到完整的饿了么(18)购物车详细信息的展示与删除
  • 干货 | 以太坊Mist负责人教你建立无服务器应用
  • 函数式编程与面向对象编程[4]:Scala的类型关联Type Alias
  • 聊聊sentinel的DegradeSlot
  • 前端攻城师
  • 入职第二天:使用koa搭建node server是种怎样的体验
  • 深入浏览器事件循环的本质
  • 实习面试笔记
  • 微信开源mars源码分析1—上层samples分析
  • 想写好前端,先练好内功
  • 项目实战-Api的解决方案
  • 协程
  • 一个SAP顾问在美国的这些年
  • 基于django的视频点播网站开发-step3-注册登录功能 ...
  • 小白应该如何快速入门阿里云服务器,新手使用ECS的方法 ...
  • 曜石科技宣布获得千万级天使轮投资,全方面布局电竞产业链 ...
  • ​Kaggle X光肺炎检测比赛第二名方案解析 | CVPR 2020 Workshop
  • ​sqlite3 --- SQLite 数据库 DB-API 2.0 接口模块​
  • #pragma data_seg 共享数据区(转)
  • (2)MFC+openGL单文档框架glFrame
  • (3)llvm ir转换过程
  • (Arcgis)Python编程批量将HDF5文件转换为TIFF格式并应用地理转换和投影信息
  • (k8s中)docker netty OOM问题记录
  • (Mac上)使用Python进行matplotlib 画图时,中文显示不出来
  • (补)B+树一些思想
  • (第一天)包装对象、作用域、创建对象
  • (一)使用Mybatis实现在student数据库中插入一个学生信息
  • .cn根服务器被攻击之后
  • .NET CORE 2.0发布后没有 VIEWS视图页面文件
  • .NET 常见的偏门问题