律师事务所东莞网站建设,微商如何做网站引流,报社网站建设方案,互联网广告目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介… 目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 给定两个数组arr1arr2求arr1和arr2合并到一起后第k小的数是什么 如 arr1 [1,2,3] arr2 [3,4,5,6] 求第3小的数 结果为3
解决方案
原问题 参考相同长度的排序数组求上中位数的解法 https://editor.csdn.net/md?not_checkout1articleId131177400 接下来介绍如何将两个长度不相同的排序数组能够套用上面的办法 首先假设短数组长度10 [0…9] 长数组长度27 [0…26] 总长度为37
如果第k小的数中kshor.len ,也就是k 10,那么长数组中角标大于k的部分是不会存在第k小的数的因为后面的数至少都大于k个数所以问题就变成了 arr1[0…k-1] 和arr2[0…k-1]之间求第k小的数问题了,套用参考即可如果第k小的数范围在 37 - 10 k 37 之间时 我们知道k后面最多只能有9个数所以短数组都能选择长数组可以选的范围只能是27-10到27的范围之间问题又变成了相同长度数组求上中位数的问题套用参考即可最后k如果都不满足上面的条件也就是 10k37-10该怎么办呢我们假设k 1616前面必须有15个数后面必须有20个数那么现在我们看下如何补齐。前面15个数短数组如果全补上去还剩5个数需要长数组填那么长数组从第5个位置开始比较查看是否真的短数组需要补上去(短数组的最大值 长数组的第5个位置)如果不小于则从第6个位置开始计算 后面20个如果将短数组全补上去还剩10个需要补所以长数组中最多能到低16个开始往回走我们发现长度刚好是10直接套用公式即可。
代码编写
java语言版本
原问题 原问题 /*** 二轮测试两个排序数组中找到第k小的数* return*/public static int findKMinFromSortArrCp1(int[] arr1, int[] arr2, int k) {if (k 1|| arr1 null || arr2 null || arr1.length 0 || arr2.length 0|| (arr1.length arr2.length k)) {throw new RuntimeException(非法入参);}int[][] compareRes compareArr(arr1, arr2);int[] shortArr compareRes[0];int[] longArr compareRes[1];if (k shortArr.length) {return getUpMidFromSameLenArr(shortArr, 0, k-1, longArr, 0, k-1);}else if (k longArr.length) {// 后面需要有几个元素int sub (shortArr.length longArr.length) - k;int start1 shortArr.length - 1 - sub;int start2 longArr.length - 1 - sub;if (longArr[start2] shortArr[shortArr.length - 1]) {return longArr[start2];}if (longArr[shortArr.length - 1] shortArr[start1]) {return longArr[shortArr.length-1];}return getUpMidFromSameLenArr(shortArr, start11, shortArr.length-1, longArr, start21, longArr.length-1);}else {int sub (shortArr.length longArr.length) - k;// 后面必须凑够20个int start2 k - shortArr.length - 1;// 排除一个值否则长度不相等if (shortArr[shortArr.length - 1] longArr[start2]) {return longArr[start2];}else {start2;}int end2 longArr.length - (sub - shortArr.length) - 1;return getUpMidFromSameLenArr(shortArr, 0, shortArr.length-1, longArr, start2, end2);}}/*** 从两个数组中相同长度的子数组部分中求上中位数* param arr1* param start1* param end1* param arr2* param start2* param end2* return*/private static int getUpMidFromSameLenArr(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2) {int mid1 0;int mid2 0;while (start1 end1) {// 获取中间值mid1 (start1 end1)/2;mid2 (start2 end2)/2;if (arr1[mid1] arr1[mid2]) {return arr1[mid1];}else {// 计算长度偶数或者奇数偶数0奇数1int offset ((end1 - start1 1) 1) ^ 1;if (arr1[mid1] arr2[mid2]) {// 奇数的话不需要调整数组大小直接割end1 mid1;start2 mid2 offset;}else {start1 mid1 offset;end2 mid2;}}}return Math.min(arr1[start1], arr2[start2]);}/*** 比较出来两个数组的长短* param arr1* param arr2* return compareRes[0] 为短数组*/private static int[][] compareArr(int[] arr1, int[] arr2) {return arr1.length arr2.length ? new int[][]{arr2, arr1} : new int[][]{arr1, arr2};}public static void main(String[] args) {System.out.println(findKMinFromSortArrCp1(new int[]{1,2,3}, new int[]{3,4,5,6}, 6));}c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
这道题最后分析的地方为什么能够恰好是10呢这个我仔细想了一下 首先 长数组的起始位置 k-10 结束位置27-((37-k)-10) k 那么结束位置 - 起始位 10 短数组长度
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
