当前位置：首页 > news >正文

石家庄外贸网站建设公司排名百度关键词搜索排名查询

news 2025/7/16 23:58:34

石家庄外贸网站建设公司排名,百度关键词搜索排名查询,网站的网络公司,一个微信公众号可以做几个网站目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识！ 问题介…

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定两个数组arr1，arr2，求arr1和arr2合并到一起后，第k小的数是什么
如：
arr1 = [1,2,3]
arr2 = [3,4,5,6]
求第3小的数
结果为3

解决方案

原问题：
参考相同长度的排序数组求上中位数的解法：

https://editor.csdn.net/md?not_checkout=1&articleId=131177400

接下来介绍如何将两个长度不相同的排序数组能够套用上面的办法
首先假设短数组长度10 [0…9]
长数组长度27 [0…26]
总长度为37

如果第k小的数中k<shor.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如果都不满足上面的条件，也就是 10<k<37-10，该怎么办呢？我们假设k = 16，16前面必须有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, start1+1, shortArr.length-1, longArr, start2+1, 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));}