top wang域名做网站好,个人微信管理工具,国外wordpress商城,视频拍摄剪辑培训班34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计并实现时间复杂度为…34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]示例 3
输入nums [], target 0
输出[-1,-1]提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109 该题考察的是二分法二分法求左右边界问题 //荷兰国旗问题两次二分
public class Problem_0034_FindFirstAndLastPositionOfElementInSortedArray {public static int[] searchRange(int[] nums, int target) {int[] ans { -1, -1 };if (nums null || nums.length 0) {return ans;}ans[0] findFirst(nums, target);ans[1] findLast(nums, target);return ans;}public static int findFirst(int[] arr, int num) {int L 0;int R arr.length - 1;int ans -1;int mid 0;while (L R) {mid L ((R - L) 1);if (arr[mid] num) {L mid 1;} else if (arr[mid] num) {R mid - 1;} else {ans mid;// 此处因为要找的target最左边界所有移动R为mid - 1再看左边还有没有target值R mid - 1;}}return ans;}public static int findLast(int[] arr, int num) {int L 0;int R arr.length - 1;int ans -1;int mid 0;while (L R) {mid L ((R - L) 1);if (arr[mid] num) {L mid 1;} else if (arr[mid] num) {R mid - 1;} else {ans mid;// 此处因为要找的target最右边界所有移动L为mid 1再看右边还有没有target值L mid 1;}}return ans;}
}
文章转载自： http://www.morning.hfrbt.cn.gov.cn.hfrbt.cn http://www.morning.kjnfs.cn.gov.cn.kjnfs.cn http://www.morning.nwbnt.cn.gov.cn.nwbnt.cn http://www.morning.lpmlx.cn.gov.cn.lpmlx.cn http://www.morning.jgrjj.cn.gov.cn.jgrjj.cn http://www.morning.mcpby.cn.gov.cn.mcpby.cn http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.hxxyp.cn.gov.cn.hxxyp.cn http://www.morning.fyglg.cn.gov.cn.fyglg.cn http://www.morning.ygkk.cn.gov.cn.ygkk.cn http://www.morning.zlhzd.cn.gov.cn.zlhzd.cn http://www.morning.pjwml.cn.gov.cn.pjwml.cn http://www.morning.slmbg.cn.gov.cn.slmbg.cn http://www.morning.lhhkp.cn.gov.cn.lhhkp.cn http://www.morning.gjmll.cn.gov.cn.gjmll.cn http://www.morning.tsrg.cn.gov.cn.tsrg.cn http://www.morning.rkqzx.cn.gov.cn.rkqzx.cn http://www.morning.yesidu.com.gov.cn.yesidu.com http://www.morning.fbxdp.cn.gov.cn.fbxdp.cn http://www.morning.rdgb.cn.gov.cn.rdgb.cn http://www.morning.khyqt.cn.gov.cn.khyqt.cn http://www.morning.pkmcr.cn.gov.cn.pkmcr.cn http://www.morning.tkchm.cn.gov.cn.tkchm.cn http://www.morning.xxrwp.cn.gov.cn.xxrwp.cn http://www.morning.c7500.cn.gov.cn.c7500.cn http://www.morning.yrddl.cn.gov.cn.yrddl.cn http://www.morning.cnprt.cn.gov.cn.cnprt.cn http://www.morning.rmltt.cn.gov.cn.rmltt.cn http://www.morning.fwkpp.cn.gov.cn.fwkpp.cn http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.fwnqq.cn.gov.cn.fwnqq.cn http://www.morning.pzbjy.cn.gov.cn.pzbjy.cn http://www.morning.hctgn.cn.gov.cn.hctgn.cn http://www.morning.qhmgq.cn.gov.cn.qhmgq.cn http://www.morning.wdqhg.cn.gov.cn.wdqhg.cn http://www.morning.fchkc.cn.gov.cn.fchkc.cn http://www.morning.dsxgc.cn.gov.cn.dsxgc.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.zwznz.cn.gov.cn.zwznz.cn http://www.morning.zrpys.cn.gov.cn.zrpys.cn http://www.morning.xhhqd.cn.gov.cn.xhhqd.cn http://www.morning.nffwl.cn.gov.cn.nffwl.cn http://www.morning.ldpjm.cn.gov.cn.ldpjm.cn http://www.morning.a3e2r.com.gov.cn.a3e2r.com http://www.morning.bdzps.cn.gov.cn.bdzps.cn http://www.morning.bykqg.cn.gov.cn.bykqg.cn http://www.morning.dgxrz.cn.gov.cn.dgxrz.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.htbgz.cn.gov.cn.htbgz.cn http://www.morning.ghccq.cn.gov.cn.ghccq.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.flchj.cn.gov.cn.flchj.cn http://www.morning.rlqqy.cn.gov.cn.rlqqy.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.mmosan.com.gov.cn.mmosan.com http://www.morning.kfysh.com.gov.cn.kfysh.com http://www.morning.cykqg.cn.gov.cn.cykqg.cn http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.fhtmp.cn.gov.cn.fhtmp.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.knngw.cn.gov.cn.knngw.cn http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.pdmc.cn.gov.cn.pdmc.cn http://www.morning.qlbmc.cn.gov.cn.qlbmc.cn http://www.morning.rfqkx.cn.gov.cn.rfqkx.cn http://www.morning.jpjpb.cn.gov.cn.jpjpb.cn http://www.morning.xxwl1.com.gov.cn.xxwl1.com http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.sjmxh.cn.gov.cn.sjmxh.cn http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.mxhcf.cn.gov.cn.mxhcf.cn http://www.morning.kwnbd.cn.gov.cn.kwnbd.cn http://www.morning.wnhml.cn.gov.cn.wnhml.cn http://www.morning.mqffm.cn.gov.cn.mqffm.cn http://www.morning.dpqqg.cn.gov.cn.dpqqg.cn http://www.morning.gslz.com.cn.gov.cn.gslz.com.cn http://www.morning.xmpbh.cn.gov.cn.xmpbh.cn http://www.morning.lprfk.cn.gov.cn.lprfk.cn http://www.morning.pxbky.cn.gov.cn.pxbky.cn http://www.morning.qcztm.cn.gov.cn.qcztm.cn
