求两个等长有序数组的中位数的logN算法 分治法

http://blog.csdn.net/yangliuy/article/details/7194199

题目:有两个长为n的非递减数组A和B,把B接在A的后面变成长为2n的数组C。设计算法求C的中位数(第n小数)。

思路:O(n)的算法很容易找到,关键是用二分的思想设计logn算法。这题关键是用好a和b数组中脚标和为定值的元素的大小关系。

            直观想法是:如果中位数在数组a中,那么若a[m]<b[n-m-2],此时比a[m]小的数最多只有n-2个,即a[m]不可能为第n小数,偏小更新左界;若a[m]> b [n-m-1],此时比a[m]小的数至少有n个,a[m]不可能为第n小数,偏大更新右界;若a[m]介于b[n-m-2]与b [n-m-1]则a[m]恰好为第n小数。 中位数在数组b中的情况类似。

[cpp] view plaincopy

 #include <iostream> 
 using namespace std;  
  
 int findNthNumber(int a[], int b[], int n){  
  int l = 0, r = n -1;  
  int m;  
  while(l <= r){  
         m = (l + r) / 2;  
  if(m == n - 1 || a[m] < b[n - m -2]){  
  //此时比a[m]小的数最多只有n-2个,即a[m]不可能为第n小数,偏小更新左界 
             l = m + 1;  
         }  
  else if (a[m] < b [n - m - 1]){  
  //此时比a[m]小的数恰好有n-1个,a[m]就是第n小数,返回 
  return a[m];  
         }  
  else r = m - 1;//此时比a[m]小的数至少有n个,即a[m]不可能为第n小数,偏大更新右界 
     }  
  //中位数在b数组中的情况,和上面类似 
     l = 0, r = n -1;  
  while(l <= r){  
         m = (l + r) / 2;  
  if(m == n - 1 || b[m] < a[n - m -2]){  
             l = m + 1;  
         }  
  else if (b[m] < a [n - m - 1]){  
  return b[m];  
         }  
  else r = m - 1;  
     }  
 }  
  
 int main(){  
  int  a[] = {1, 3, 4, 9, 11, 20, 21};  
  int  b[] = {2, 7, 8, 10, 70, 76, 79};  
     cout<<findNthNumber(a, b, 7)<<endl;   
  return 0;  
 }  

也可以取a[m]与b[n-m-2]中较大的一个,然后与a[m+1]和b[n-m-1]作比较,简化后的代码如下

[cpp] view plaincopy

 #include <iostream> 
 using namespace std;  
  
 int findNthNumber(int a[], int b[], int n){  
  int l = 0, r = n -1;  
  int m, tmp;  
  while(l <= r){  
         m = (l + r) / 2;  
         tmp = (a[m] < b [n - m - 2] ? b[n - m - 2] : a[m]);  
  //tmp取a[m]与b[n-m-2]中较大的一个,然后与a[m+1]和b[n-m-1]作比较 
  if(tmp > b [n - m - 1]){  
             r = m - 1;  
         }  
  else if(tmp > a [m + 1]){  
             l = m + 1;  
         }  
  else return tmp;  
     }  
 }  
  
 int main(){  
  int  a[] = {1, 3, 10, 11, 12, 20, 21};  
  int  b[] = {2, 7, 8, 9, 70, 76, 79};  
     cout<<findNthNumber(a, b, 7)<<endl;   
  return 0;  
 }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

怎样才能学好java?

Java是一种计算机编程语言,拥有跨平台、面向对象、泛型编程的特性,广泛应用于企业级Web应用开发和移动应用开发,是目前用的最广的语言之一,在编程语言排行榜多次...

2995
来自专栏数据结构与算法

HDU3440 House Man

题意:有n栋房子,给出每栋房子的高度和开始时的相对位置,可以移动一些房子,但不能改变这些房子的相对位置,现在从最矮的房子开始,每次跳至比它高的第一栋房子, 而且...

2856
来自专栏老九学堂

Java微课堂之基本选择结构(1)

基本选择结构知识点1 boolean用法和关系运算符 这一讲主要的是给Java语法中的选择结构做一个前导知识点的讲解。 boolean数据类型是Java中的布尔...

3565
来自专栏Petrichor的专栏

pytorch: tensor类型的构建与相互转换

其中,torch.Tensor、torch.rand、torch.randn 均默认生成 torch.FloatTensor型 :

2076
来自专栏专知

【Code】关关的刷题日记21——Leetcode 485. Max Consecutive Ones

关小刷刷题 21——Leetcode 485. Max Consecutive Ones 题目 Given a binary array, find the m...

29510
来自专栏程序员互动联盟

【面试宝典】谈谈面向对象

面试官:知道面向对象吧。 小白:嗯,知道,面想对象就是封装继承多态呀。 面试官:回答了一部分,还能谈谈除了封装、继承、多态之外的吗,比如说怎么抽象,抽象的思想是...

4048
来自专栏数据结构与算法

1074 食物链 2001年NOI全国竞赛

1074 食物链 2001年NOI全国竞赛 时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 题目描述 Des...

3506
来自专栏编程

零基础学习人工智能之Python篇1-Python定义

学习Python首先咱要明白Python是什么 定义: Python是一种面向对象的解释型计算机程序设计语言 我们分解下Python的定义,主要是要理解面向对象...

2126
来自专栏蜉蝣禅修之道

Apriori算法的Python实现

2684
来自专栏我是业余自学C/C++的

redis_3.0.7_sds.h_sdslen()

1963

扫码关注云+社区

领取腾讯云代金券