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);
}
}
欢迎提出更优化的解决方案,谢谢!
分享到:
相关推荐
5.5 如何去除有序数组的重复元素本文对应的力扣题目:26.删除排序数组中的重复项83.删除排序链表中的重复元素删除排序数组中的重复项:// 长度为索引 + 1
分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include #include <algorithm> #...
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下载 [toc] 一、题目 Q1 等差数列求和 ...在一个无序数组中,任意相邻两个数不等 局部最小数:这个数比它的左边和右边都小,这个数被称为局部最小 问题:找到任意一个(随便一个)局部最小的
两个有序数组合并为一个有序数组 Java 实现 : 空间复杂度 O(1);时间复杂度 最好 O(m + n) 最坏 O(mn) 空间复杂度 O(m);时间复杂度 O(m + n) LeetCode#999 链表 单链表 Java实现 及 实现了链表的反转 双向链表 ...
剑指 Offer 03. 数组中重复的数字原地置换,时间空间100%= i: # while 条件 是 符合排序后的条件还有个二分法的情况,暂时看不懂。
( 例如,数组 [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是一个npm模块,用于查找两个数组的公共部分或不同部分,它基于LCS(最长公共子序列)问题的解决方案,广泛用于两个数组的diff / patch(例如diff / patch功能)。 git)。 该模块的...
青蛙过河leetcode 切题 Clarification 明确题目要求 Possible solutions 所有可能解法 compare (time/space) optimal ...第一遍 ...第二遍 ...第三遍 ...第四遍 ...第五遍 ...合并两个有序数组 141 环形链表 189 旋转
合并两个有序链表 删除链表的节点 反转链表 合并两个排序的链表 19.删除链表的倒数第N个节点 链表中倒数第k个节点 面试题 02.05. 链表求和 55.跳跃游戏 45.跳跃游戏 II 21.买卖股票的最佳时机 122.买卖股票的最佳...
赠送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; ...
思路:双指针法定义两个指针left和right,初始化时分别指向数组的两端如果left和right对应的值加起来等于target,那么可直接返回。因为数组是排序
4:寻找两个正序数组的中位数 5:最长回文子串 10:正则表达式匹配 11:盛水最多的容器 15:三数之和 16:最接近的三数之和 17:电话号码的字母组合 19:删除链表的倒数第N个节点 20:有效的括号 21:合并两个有序...
java.lang.RuntimeException: Unsupported algorithm: HmacSHA1 解决方法,阿里云
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 选择...
从一个每行每列都排序好的矩阵中找K要求时间复杂度为O(N + M),空间复杂度为O(1)//从右上角开始,【如果比K大,说明下面的数不可能,往左;如果比K小,说
一种求线段交的最优算法,时间复杂度O(nlogn+k),空间复杂度O(n),k为交点个数。
产生可能的集合 68 30.Algorithm Gossip: m元素集合的n个元素子集 71 31.Algorithm Gossip: 数字拆解 73 32.Algorithm Gossip: 得分排行 76 33.Algorithm Gossip: 选择、插入、气泡排序 78 34....
1.河内之塔.. 2.Algorithm Gossip: 费式数列. 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官(一) 6.Algorithm Gossip: 老鼠走迷... 21.Algorithm Gossip: 最大访客数等等经典问题详解
建议牛客上的剑指offer,先刷完数组力扣1:两数之和力扣1299:将每个元素替换为右侧最大元素力扣1464:数组中两个元素的最大乘积力扣15:三数之和力扣179:最大数力扣189:旋转数组力扣215:数组中第K个最大元素力扣...