`
YuHuang.Neil
  • 浏览: 179722 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Algorithm 04 : 寻找两个有序数组中的第N个数,要求时间复杂度为O(logm+logn)

阅读更多
Question : Give a divide and conquer algorithm for the following problem : you are
                 given two sorted lists of size m and n, and are allowed unit time access
                 to the ith element of each list. Given an O(logm+logn) time algorithm for
                 computing the kth largest element in the union of the two lists.
                 (For simplicity, you can assume that the elements of the two lists are
                 distinct).

问题:寻找两个有序数组中的第N个数,要求时间复杂度为O(logm+logn)。



/**
  * @author YuHuang
  * @vision 2011-10-04
  * This program is only for algorithm training.
  *
  */

import java.lang.RuntimeException;

public class SearchKthNumber {

        private int[] aArray;
        private int[] bArray;

        public SearchKthNumber(int[] aArray,int[] bArray){
                this.aArray=aArray;
                this.bArray=bArray;
                if(this.aArray==null||this.bArray==null){
                        throw new RuntimeException("Array should not be null!");
                }
        }

        public int doSearch(int aLeft,int aRight,int bLeft,int bRight,int k){
                int aMiddle = (aLeft+aRight)/2;
                int bMiddle = (bLeft+bRight)/2;

                if(aLeft>aRight){
                        return bArray[bLeft+k-1];
                }

                if(bLeft>bRight){
                        return aArray[aLeft+k-1];
                }

                if(aArray[aMiddle]>bArray[bMiddle]){
                        if(k<=(aMiddle-aLeft)+(bMiddle-bLeft)+1){
                                return doSearch(aLeft,aMiddle-1,bLeft,bRight,k);
                        }else{
                                return doSearch(aLeft,aRight,bMiddle+1,bRight,k-(bMiddle-bLeft)-1);
                        }
                }else{
                        if(k<=((aMiddle-aLeft)+(bMiddle-bLeft)+1)){
                                return doSearch(aLeft,aRight,bLeft,bMiddle-1,k);
                        }else{
                                return doSearch(aMiddle+1,aRight,bLeft,bRight,k-(aMiddle-aLeft)-1);
                        }
                }
        }


        public static void main(String[] args){
                int[] aArray=new int[]{1,3,5,6,8,9,11,18,20};
                int[] bArray=new int[]{2,4,7,16,22,29,39,40,55,100};

                SearchKthNumber sn=new SearchKthNumber(aArray,bArray);
                int k=2;
                int result=sn.doSearch(0,aArray.length-1,0,bArray.length-1,k);
                System.out.println("The "+k+"th"+" Number : "+result);
        }

}





欢迎提出更优化的解决方案,谢谢!

分享到:
评论

相关推荐

    DeShuiYu#labuladong_algorithm#如何去除有序数组的重复元素1

    5.5 如何去除有序数组的重复元素本文对应的力扣题目:26.删除排序数组中的重复项83.删除排序链表中的重复元素删除排序数组中的重复项:// 长度为索引 + 1

    C语言实现在数组A上有序合并数组B的方法

    分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include #include &lt;algorithm&gt; #...

    C++ STL开发技术导引(第5章)

    23.13 第n个元素nth_element 384 23.14 下确界lower_bound 386 23.15 上确界upper_bound 388 23.16 等价区间equal_range 390 23.17 折半搜索binary_search 392 23.18 子集合includes 393 23.19 集合求...

    leetcode下载-Algorithm:算法题积累

    leetcode下载 [toc] 一、题目 Q1 等差数列求和 ...在一个无序数组中,任意相邻两个数不等 局部最小数:这个数比它的左边和右边都小,这个数被称为局部最小 问题:找到任意一个(随便一个)局部最小的

    javalruleetcode-algorithm:《数据结构与算法之美》练习

    两个有序数组合并为一个有序数组 Java 实现 : 空间复杂度 O(1);时间复杂度 最好 O(m + n) 最坏 O(mn) 空间复杂度 O(m);时间复杂度 O(m + n) LeetCode#999 链表 单链表 Java实现 及 实现了链表的反转 双向链表 ...

    TQCAI#Algorithm#剑指 Offer 03. 数组中重复的数字1

    剑指 Offer 03. 数组中重复的数字原地置换,时间空间100%= i: # while 条件 是 符合排序后的条件还有个二分法的情况,暂时看不懂。

    geekerstar#algorithm-tutorial#寻找旋转排序数组中的最小值1

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。示例 1:输入: [3,4,5,1,2]输出: 1示例 2:输入:

    fast-array-diff:节点模块查找两个数组的相同差异

    快速数组差异 fast-array-diff是一个npm模块,用于查找两个数组的公共部分或不同部分,它基于LCS(最长公共子序列)问题的解决方案,广泛用于两个数组的diff / patch(例如diff / patch功能)。 git)。 该模块的...

    青蛙过河leetcode-algorithm:刷题记录

    青蛙过河leetcode 切题 Clarification 明确题目要求 Possible solutions 所有可能解法 compare (time/space) optimal ...第一遍 ...第二遍 ...第三遍 ...第四遍 ...第五遍 ...合并两个有序数组 141 环形链表 189 旋转

    leetcode数组下标大于间距-my-algorithm:我的算法

    合并两个有序链表 删除链表的节点 反转链表 合并两个排序的链表 19.删除链表的倒数第N个节点 链表中倒数第k个节点 面试题 02.05. 链表求和 55.跳跃游戏 45.跳跃游戏 II 21.买卖股票的最佳时机 122.买卖股票的最佳...

    pentaho-aggdesigner-algorithm-5.1.5-jhyde-API文档-中文版.zip

    赠送jar包:pentaho-aggdesigner-algorithm-5.1.5-jhyde.jar; 赠送原API文档:pentaho-aggdesigner-algorithm-5.1.5-jhyde-javadoc.jar; 赠送源代码:pentaho-aggdesigner-algorithm-5.1.5-jhyde-sources.jar; ...

    wyh317#Algorithm_solving#167.两数之和 II - 输入有序数组1

    思路:双指针法定义两个指针left和right,初始化时分别指向数组的两端如果left和right对应的值加起来等于target,那么可直接返回。因为数组是排序

    javalruleetcode-Algorithm-Demo:算法的各类实现

    4:寻找两个正序数组的中位数 5:最长回文子串 10:正则表达式匹配 11:盛水最多的容器 15:三数之和 16:最接近的三数之和 17:电话号码的字母组合 19:删除链表的倒数第N个节点 20:有效的括号 21:合并两个有序...

    java.lang.RuntimeException: Unsupported algorithm: HmacSHA1解决方法

    java.lang.RuntimeException: Unsupported algorithm: HmacSHA1 解决方法,阿里云

    leetcode切割分组-java_algorithm:排序算法演示

    java_algorithm this is a sorting algorithm demo. created by InterlliJ. that is the java main program. ! com.sample.sort包下 平均时间复杂度 O(n^2) 空间复杂度 O(1) BubbleSort 冒泡排序 SelectionSort 选择...

    cyxpdc#Algorithm#从排序矩阵中找数1

    从一个每行每列都排序好的矩阵中找K要求时间复杂度为O(N + M),空间复杂度为O(1)//从右上角开始,【如果比K大,说明下面的数不可能,往左;如果比K小,说

    An optimal algorithm for finding segment intersections

    一种求线段交的最优算法,时间复杂度O(nlogn+k),空间复杂度O(n),k为交点个数。

    经典算法大全.pdf

    产生可能的集合 68 30.Algorithm Gossip: m元素集合的n个元素子集 71 31.Algorithm Gossip: 数字拆解 73 32.Algorithm Gossip: 得分排行 76 33.Algorithm Gossip: 选择、插入、气泡排序 78 34....

    Java经典问题算法大全

    1.河内之塔.. 2.Algorithm Gossip: 费式数列. 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官(一) 6.Algorithm Gossip: 老鼠走迷... 21.Algorithm Gossip: 最大访客数等等经典问题详解

    high-frequency-algorithm:公司面试算法高频真题

    建议牛客上的剑指offer,先刷完数组力扣1:两数之和力扣1299:将每个元素替换为右侧最大元素力扣1464:数组中两个元素的最大乘积力扣15:三数之和力扣179:最大数力扣189:旋转数组力扣215:数组中第K个最大元素力扣...

Global site tag (gtag.js) - Google Analytics