河北提供网站制作公司电话,网站开发查找漏洞的工具,微信开发者版是什么意思,模板之家官网中文目录 1- 思路题目识别二分 2- 实现⭐4. 寻找两个正序数组的中位数——题解思路 3- ACM 实现 原题链接#xff1a;4. 寻找两个正序数组的中位数 1- 思路
题目识别
识别1 #xff1a;给定两个数组 nums1 和 nums2 #xff0c;找出数组的中位数
二分
思路
将寻找中位数 —… 目录 1- 思路题目识别二分 2- 实现⭐4. 寻找两个正序数组的中位数——题解思路 3- ACM 实现 原题链接4. 寻找两个正序数组的中位数 1- 思路
题目识别
识别1 给定两个数组 nums1 和 nums2 找出数组的中位数
二分
思路
将寻找中位数 —— 寻找两个合并数组的第 K 大 K代表中位数
实现
① 遍历两个数组 通过比较两个数组的第 [k/2] 个元素 如果 numsA[k/2] numsB[k/2] 的时候删除 numsA 的前半部分元素。② 找剩余的k/2 个元素
其实现思路在于始终让 nums1 为元素数量少的数组 2- 实现
⭐4. 寻找两个正序数组的中位数——题解思路 class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 1. 长度int len1 nums1.length;int len2 nums2.length;// 定义 right// 排除奇、偶 影响int left (len1len21)/2;int right (len1len22)/2;return ((findK(nums1,0,len1-1,nums2,0,len2-1,left) findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);}public int findK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 始终让 nums2 最长int len1 end1 - start11;int len2 end2 - start21;if(len1len2) return findK(nums2,start2,end2,nums1,start1,end1,k);// 判断if(len10) return nums2[start2k-1];if(k 1) return Math.min(nums1[start1],nums2[start2]);// 递归逻辑int i start1 (Math.min(len1,k/2)-1);int j start2 (Math.min(len2,k/2)-1);if(nums1[i] nums2[j]){return findK(nums1,start1,end1,nums2,j1,end2,k-(j-start21));}else{return findK(nums1,i1,end1,nums2,start2,end2,k-(i-start11));}}
}3- ACM 实现
public class findM {public static double findMid(int[] nums1,int[] nums2){int len1 nums1.length;int len2 nums2.length;int left (len1len21)/2;int right (len1len22)/2;return ((findK(nums1,0,len1-1,nums2,0,len2-1,left) findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);}private static double findK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 递归终止int len1 end1 - start1 1;int len2 end2 - start2 1;if(len1len2) return findK(nums2,start2,end2,nums1,start1,end1,k);// 终止if(len10) return nums2[start2k-1];if(k 1) return Math.min(nums1[start1],nums2[start2]);// 递归int i start1 (Math.min(len1,k/2)-1);int j start2 (Math.min(len2,k/2)-1);if(nums1[i] nums2[j]){return findK(nums1,start1,end1,nums2,j1,end2,k - (j-start21));}else{return findK(nums1,i1,end1,nums2,start2,end2,k-(i-start11));}}public static void main(String[] args) {Scanner sc new Scanner(System.in);String input sc.nextLine();input input.replace([,).replace(],);String input2 sc.nextLine();input2 input2.replace([,).replace(],);String[] parts input.split(,);int[] nums new int[parts.length];for(int i 0 ; i nums.length;i){nums[i] Integer.parseInt(parts[i]);}String[] parts2 input2.split(,);int[] nums2 new int[parts.length];for(int i 0 ; i nums2.length;i){nums2[i] Integer.parseInt(parts2[i]);}System.out.println(结果是findMid(nums,nums2));}
}
文章转载自： http://www.morning.pqchr.cn.gov.cn.pqchr.cn http://www.morning.jwxnr.cn.gov.cn.jwxnr.cn http://www.morning.bpmtx.cn.gov.cn.bpmtx.cn http://www.morning.hbhnh.cn.gov.cn.hbhnh.cn http://www.morning.rdlong.com.gov.cn.rdlong.com http://www.morning.ntgrn.cn.gov.cn.ntgrn.cn http://www.morning.zhmgcreativeeducation.cn.gov.cn.zhmgcreativeeducation.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.fxzgw.com.gov.cn.fxzgw.com http://www.morning.sjsks.cn.gov.cn.sjsks.cn http://www.morning.qkkmd.cn.gov.cn.qkkmd.cn http://www.morning.pfgln.cn.gov.cn.pfgln.cn http://www.morning.zlces.com.gov.cn.zlces.com http://www.morning.ldnrf.cn.gov.cn.ldnrf.cn http://www.morning.qytby.cn.gov.cn.qytby.cn http://www.morning.csgwd.cn.gov.cn.csgwd.cn http://www.morning.dndk.cn.gov.cn.dndk.cn http://www.morning.xwgbr.cn.gov.cn.xwgbr.cn http://www.morning.zjcmr.cn.gov.cn.zjcmr.cn http://www.morning.rlwgn.cn.gov.cn.rlwgn.cn http://www.morning.dpnhs.cn.gov.cn.dpnhs.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.mxtjl.cn.gov.cn.mxtjl.cn http://www.morning.rghkg.cn.gov.cn.rghkg.cn http://www.morning.lgnbr.cn.gov.cn.lgnbr.cn http://www.morning.mnsmb.cn.gov.cn.mnsmb.cn http://www.morning.dtmjn.cn.gov.cn.dtmjn.cn http://www.morning.thpns.cn.gov.cn.thpns.cn http://www.morning.wtrjq.cn.gov.cn.wtrjq.cn http://www.morning.oumong.com.gov.cn.oumong.com http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.ruifund.com.gov.cn.ruifund.com http://www.morning.gbrdx.cn.gov.cn.gbrdx.cn http://www.morning.cptzd.cn.gov.cn.cptzd.cn http://www.morning.ftwlay.cn.gov.cn.ftwlay.cn http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.nkwgy.cn.gov.cn.nkwgy.cn http://www.morning.rxpp.cn.gov.cn.rxpp.cn http://www.morning.bssjp.cn.gov.cn.bssjp.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.qstkk.cn.gov.cn.qstkk.cn http://www.morning.rfwqt.cn.gov.cn.rfwqt.cn http://www.morning.rqxch.cn.gov.cn.rqxch.cn http://www.morning.zmyzt.cn.gov.cn.zmyzt.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.zqfz.cn.gov.cn.zqfz.cn http://www.morning.hhzdj.cn.gov.cn.hhzdj.cn http://www.morning.ghwdm.cn.gov.cn.ghwdm.cn http://www.morning.rymb.cn.gov.cn.rymb.cn http://www.morning.pskjm.cn.gov.cn.pskjm.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.mgskc.cn.gov.cn.mgskc.cn http://www.morning.dgng.cn.gov.cn.dgng.cn http://www.morning.rsfp.cn.gov.cn.rsfp.cn http://www.morning.qrmyd.cn.gov.cn.qrmyd.cn http://www.morning.jgmlb.cn.gov.cn.jgmlb.cn http://www.morning.cbpmq.cn.gov.cn.cbpmq.cn http://www.morning.jbblf.cn.gov.cn.jbblf.cn http://www.morning.wkgyz.cn.gov.cn.wkgyz.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.tkgjl.cn.gov.cn.tkgjl.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com http://www.morning.lmjkn.cn.gov.cn.lmjkn.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.ndtzy.cn.gov.cn.ndtzy.cn http://www.morning.cqyhdy.cn.gov.cn.cqyhdy.cn http://www.morning.gfpyy.cn.gov.cn.gfpyy.cn http://www.morning.xgchm.cn.gov.cn.xgchm.cn http://www.morning.gxwyr.cn.gov.cn.gxwyr.cn http://www.morning.mpngp.cn.gov.cn.mpngp.cn http://www.morning.sbjhm.cn.gov.cn.sbjhm.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.gqtzb.cn.gov.cn.gqtzb.cn http://www.morning.gczqt.cn.gov.cn.gczqt.cn http://www.morning.zwdrz.cn.gov.cn.zwdrz.cn http://www.morning.dpdr.cn.gov.cn.dpdr.cn http://www.morning.ltffk.cn.gov.cn.ltffk.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.bkqw.cn.gov.cn.bkqw.cn
