给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数 注意:上中位数指在两个数组的数个数在偶数时取更大的 数据范围:两个数组的长度都满足 ,数组中的所有值都满足-笔试面试资料

这是qklbishe.com第19277 篇笔试面试资料
提供答案分析,通过本文《给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数
注意:上中位数指在两个数组的数个数在偶数时取更大的
数据范围:两个数组的长度都满足 ,数组中的所有值都满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数
注意:上中位数指在两个数组的数个数在偶数时取更大的
数据范围:两个数组的长度都满足 给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数          注意:上中位数指在两个数组的数个数在偶数时取更大的          数据范围:两个数组的长度都满足 ,数组中的所有值都满足,数组中的所有值都满足 给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数          注意:上中位数指在两个数组的数个数在偶数时取更大的          数据范围:两个数组的长度都满足 ,数组中的所有值都满足
Java

给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数          注意:上中位数指在两个数组的数个数在偶数时取更大的          数据范围:两个数组的长度都满足 ,数组中的所有值都满足 零葬

这个题用外排的方式实现是绝对可以解的,只是直接归并的时间复杂度比较高,面试场合下并不适合聊这个算法。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param arr1 int整型一维数组       * @param arr2 int整型一维数组       * @return int整型      */     public int getUpMedian (int[] arr1, int[] arr2) {         // write code here         int index = (arr1.length + arr2.length) / 2;         if((arr1.length + arr2.length) % 2 == 0) index--;         int p1 = 0, p2 = 0, p = 0;         while(p1 < arr1.length && p2 < arr2.length){             if(arr1[p1] <= arr2[p2]){                 if(p == index) return arr1[p1];                 p1++;             }else{                 if(p == index) return arr2[p2];                 p2++;             }             p++;         }         while(p1 < arr1.length){             if(p == index) return arr1[p1];             p1++;             p++;         }         while(p2 < arr2.length){             if(p == index) return arr2[p2];             p2++;             p++;         }         return -1;     } }

因此我们可以复用上一题“NC251 多数组第K小数”的算法流程,找到第中间小的数就可以了,时间复杂度可以达到O(logn)级别。

import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param arr1 int整型一维数组       * @param arr2 int整型一维数组       * @return int整型      */     public int getUpMedian (int[] arr1, int[] arr2) {         // write code here         int index = (arr1.length + arr2.length) >>> 1;         if(((arr1.length + arr2.length) & 1) == 0) index--;         return findKthNum(arr1, arr2, index + 1);     // 注意调用此函数时没有第0小的数,rank序从1开始     }          public int findKthNum (int[] arr1, int[] arr2, int kth) {         int[] longs = arr1.length >= arr2.length ? arr1 : arr2;         int[] shorts = arr1.length < arr2.length ? arr1 : arr2;         int l = longs.length;         int s = shorts.length;         if(kth <= s){             return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);         }         if(kth > l){             if(shorts[kth - l - 1] >= longs[l - 1]){                 return shorts[kth - l - 1];             }             if(longs[kth - s - 1] >= shorts[s - 1]){                 return longs[kth - s - 1];             }             return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);         }         if(longs[kth - s - 1] >= shorts[s - 1]){             return longs[kth - s - 1];         }         return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);     }          public int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2) {         int mid1 = 0;         int mid2 = 0;         int offset = 0;         while(s1 < e1){             mid1 = (s1 + e1) / 2;             mid2 = (s2 + e2) / 2;             offset = ((e1 - s1 + 1) & 1) ^ 1;             if(a1[mid1] > a2[mid2]){                 e1 = mid1;                 s2 = mid2 + offset;             }else if (a1[mid1] < a2[mid2]){                 s1 = mid1 + offset;                 e2 = mid2;             }else{                 return a1[mid1];             }         }         return Math.min(a1[s1], a2[s2]);     } }

不仅时间复杂度指标上比直接归并更优,经过测试,直接提交后的运行时间也确实缩短了。

今天 11:36:45 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定两个升序的数组 arr1 和 arr2 ,求两个数组的上中位数 注意:上中位数指在两个数组的数个数在偶数时取更大的 数据范围:两个数组的长度都满足 ,数组中的所有值都满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情