【题目】
给定两个有序数组arr1和arr2,已知两个数组的长度分别为 m1 和 m2,求两个数组中的第 K 小数。要求时间复杂度O(log(m1 + m2))。
【举例】
例如 arr1 = [1, 2,3],arr2 = [3,4,5,6],K = 4。
则第 K 小数为 3.
例如 arr1 = [0,1,2],arr2 = [3,4,5,7,8], K = 3;
则第 K 小数为 2.
【难度】
难
解答
这道题和我上次讲的那一道题是非常非常类似的:递归打卡1:在两个长度相等的排序数组中找到上中位数,如果没看过的建议先看下,只是今天的这道题比上次的那道题少难一点,原理一样。
下面我随便讲一下原理吧:采用递归的方法不断缩小 K 的,把求第 K 小元素转化为第 (K-K/2) 小元素....我举个例子吧,比较容易理解。
我们假定 arr1 = [1, 2,3],arr2 = [3,4,5,6],K = 4。
和上一道题类似(注意:这里我们假设K从0算起,也就是有第0小元素,相当于令 K = K - 1),令
mid1 = K/2 = 1。
mid2 = K/2 = 1。
此时 arr2[mid2] > arr2[mid1],那么问题转化为在数组 arr1[mid1+1...m1]和数组 arr2[0...m2] 寻找第(K-md1-1)小的元素。
不过这里需要注意的是,有可能 k/2 的值是大于 m1 或者 m2的,所以如果 k/2 > m1 或者 m2 的话,我们直接令 md1 = m1-1 或者 md2 = m2-1 就行了。
代码如下:
// 由于中位数会受长度是奇偶数的影响,所以我们可以把问题转化为求
// ((n+m+1)/2+(n+m+2)/2)/2。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
// return (findKthNumber(nums1, 0, n-1, nums2,0,m-1,(n+m+1)/2) +
// findKthNumber(nums1, 0, m-1,nums2,0,m-1,(n+m+2)/2)) /2;
return 1;
}
public static int findKth(int[] arr1, int[] arr2, int k) {
if(arr1 == null || arr1.length < 1)
return arr2[k-1];
if(arr2 == null || arr2.length < 1)
return arr1[k-1];
// 注意这个函数的参数有7个,上面那个函数的参数只有3个,同名不同函数哈
return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
}
public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
// 递归结束条件
if(l1 > r1)
return arr2[l2 + k];
if(l2 > r2)
return arr1[l1 + k];
if (k == 0)// 注意,k == 0的结束条件与上面两个结束条件不能颠倒。
return Math.min(arr1[l1],arr2[l2]);
int md1 = l1 + k/2 < r1 ? l1 + k/2 : r1;
int md2 = l2 + k/2 < (r2 - l1) ? l2 + k/2 : r2;
if(arr1[md1] < arr2[md2])
return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - k / 2 - 1);
else if (arr1[md1] > arr2[md2])
return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - k / 2 - 1);
else
return arr1[md1];//返回arr2[md2]也可以,一样的。
}
// 测试
public static void main(String[] args) {
int[] arr1 = {1, 2, 3};
int[] arr2 = {0,4, 5, 6, 7, 8};
System.out.println(findKth(arr1, arr2, 2));
}
可以用迭代吗?当然可以,不过留给你自己。
下次我还会再出一道与这两道类似的题,不过,难度递增。总共有三道这种题,一定要自己手动写代码,一定要自己手动写代码,一定要自己手动写代码。
【递归打卡2】求两个有序数组的第K小数的更多相关文章
-
求两个有序数组的中位数或者第k小元素
问题:两个已经排好序的数组,找出两个数组合并后的中位数(如果两个数组的元素数目是偶数,返回上中位数). 设两个数组分别是vec1和vec2,元素数目分别是n1.n2. 算法1:最简单的办法就是把两个数 ...
-
求两个有序数组的中位数(4. Median of Two Sorted Arrays)
先吐槽一下,我好气啊,想了很久硬是没有做出来,题目要求的时间复杂度为O(log(m+n)),我猜到了要用二分法,但是没有想到点子上去.然后上网搜了一下答案,感觉好有罪恶感. 题目原型 正确的思路是:把 ...
-
(算法)两个有序数组的第k大的数
题目: 有两个数组A和B,假设A和B已经有序(从大到小),求A和B数组中所有数的第K大. 思路: 1.如果k为2的次幂,且A,B 的大小都大于k,那么 考虑A的前k/2个数和B的前k/2个数, 如果A ...
-
计算两个有序数组的第K大数(转)
传统解法,最直观的解法是O(m+n).直接merge两个数组,然后求第K大的数字. 如果想要时间复杂度将为O(log(m+n)).我们可以考虑从K入手.如果我们每次能够删除一个一定在第K个元素之前的元 ...
-
[LeetCode]Median of Two Sorted Arrays 二分查找两个有序数组的第k数(中位数)
二分.情况讨论 因为数组有序,所以能够考虑用二分.通过二分剔除掉肯定不是第k位数的区间.如果数组A和B当前处理的下标各自是mid1和mid2.则 1.假设A[mid1]<B[mid2], ①.若 ...
-
算法-求两个有序数组两两相加的值最小的K个数
我的思路是: 用队列, 从(0,0)開始入队,每次出队的时候,选(1,0) (0,1) 之间最小的入队,假设是相等的都入队,假设入过队的就不入了,把出队的k个不同的输出来就可以 我測试了几组数据都是 ...
-
Median of Two Sorted 求两个有序数组的中位数
中位数是把一个数的集合划分为两部分,每部分包含的数字个数相同,并且一个集合中的元素均大于另一个集合中的元素. 因此,我们考虑在一个任意的位置,将数组A划分成两部分.i表示划分数组A的位置,如果数组A包 ...
-
【medium】4. Median of Two Sorted Arrays 两个有序数组中第k小的数
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two ...
-
leetcode题目4.寻找两个有序数组的中位数(困难)
题目描述: 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2. 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n)). 你可以假设 nums1 和 ...
随机推荐
-
045医疗项目-模块四:采购单模块—采购单提交(Dao,Service,Action三层)
我们之前做的就是采购单的编辑,在采购单里面添加了药品,然后我们这篇文章要做的就是说提交这个采购单. 当我们创建完成采购单,确定采购单不再修改,需要提交采购单,由监管单位进行审核. 我们在提交这个采购单 ...
-
问题-Delphi在多线程中使用其他窗体上的控件,报“尚未调用CoInitialize”解决方法
1.uses ActiveX; 2. procedure HLCJ.Execute;begin CoInitialize(nil); //要使用的控件 CoUninitialize; ...
-
牛刀小试、用SharePoint 实现请假管理功能
转:http://www.cr173.com/html/15518_1.html "请假管理"应用,应该算是 SharePoint 的"Hello World!" ...
-
Java中组合 设计技巧 实例
关于组合 和 集成 先放两篇文章:这两篇文章写的太好了. http://blog.csdn.net/u013905744/article/details/51752044 Java的组合(持有对 ...
-
ScrollView无法滚动
ScrollView视图无法滚动 箭头所指地方应该用dp单位的数值
-
2018年高教社杯全国大学生数学建模竞赛A题解题思路
题目 先贴一下A的题目吧 A题 高温作业专用服装设计 在高温环境下工作时,人们需要穿着专用服装以避免灼伤.专用服装通常由三层织物材料构成,记为I.II.III层,其中I层与外界环境接触,III层与 ...
-
opencv学习笔记(一)
摘要:最近要做一个和图像处理有联系的项目,从此走上了学习opencv的道路. 灰度图:2维矩阵 彩色图:3维矩阵 ps:目前大部分设备都是用无符号 8 位整数(类型为 CV_8U)表示像素亮度 Mat ...
-
css制作tips提示框,气泡框,制作三角形
有时候我们的页面会需要这样的一些提示框或者叫气泡框,运用css,我们可以实现这样的效果. 为了实现上面的效果,我们首先要理解如何制作三角形. 当我们给一个DIV不同颜色的边框的时候,我们可以得到下面的 ...
-
Jsp重定向(response.sendRedirect())和转发(request.getRequestDispatcher().forward(request,r)的差别
<%@ page language="java" import="java.util.*" pageEncoding="utf-8"% ...
-
hibernate4日志配置
在平时运行程序时控制台有很对的日志打印,本文说明如何控制这些日志打印. 1.确定要使用日志的实现,我在这使用的是log4j. 2.加入log4j的api包slf4j-api.jar,log4j的转换包 ...