重庆专业网站建设首页排名,揭西网站建设,手递手个人求职信息网,全国建筑资质查询系统34.在排序数组中查找元素的第一个和最后一个位置 刷题#xff1a;https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/ 给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位…34.在排序数组中查找元素的第一个和最后一个位置 刷题https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/ 给你一个按照非递减顺序排列的整数数组 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 题目思路总结
本题要求在有序数组中找出目标值的起始和终止位置且必须在 O(log n) 时间复杂度内完成因此可以使用二分查找来实现。
我们使用一个辅助函数 lowerBound(nums, target) 实现 找第一个大于等于 target 的位置。
起始位置是 lowerBound(target)终止位置是 lowerBound(target 1) - 1即小于 target1 的最后一个位置如果 start nums.length || nums[start] ! target说明 target 不存在。 ✅ 一句话总结解法 用两次二分查找分别定位 target 的第一个出现位置和最后一个位置。 【Java 代码】
class Solution {public int[] searchRange(int[] nums, int target) {// 查找目标值的起始位置int start lowerBound(nums, target);// 如果起始位置超出数组范围 或 nums[start] 不是目标值说明不存在if (start nums.length || nums[start] ! target) {return new int[]{-1, -1};}// 查找目标值的结束位置等于 lowerBound(target1) 再往前一步int end lowerBound(nums, target 1) - 1;return new int[]{start, end};}// lowerBound查找第一个大于等于 target 的索引private int lowerBound(int[] nums, int target) {int left 0;int right nums.length - 1;// 标准二分写法while (left right) {int mid left (right - left) / 2;// 如果中间值小于目标说明目标在右边if (nums[mid] target) {left mid 1;} else {// 否则向左收缩right mid - 1;}}// 最终返回的是第一个 target 的位置return left;}
}示例运行演示
输入nums [5,7,7,8,8,10], target 8 start lowerBound(8) 3end lowerBound(9) - 1 5 - 1 4返回 [3, 4] 输入nums [5,7,7,8,8,10], target 6 start lowerBound(6) 1nums[1] 7 ! 6 → 返回 [-1, -1] 162. 寻找峰值false 刷题https://leetcode.cn/problems/find-peak-element/ 峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] nums[n] -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1
输入nums [1,2,3,1]
输出2
解释3 是峰值元素你的函数应该返回其索引 2。示例 2
输入nums [1,2,1,3,5,6,4]
输出1 或 5
解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5 其峰值元素为 6。【题目讲解】
峰值元素定义为该元素大于它左右相邻的元素。
基于二分查找的 局部单调性分析
比较中点与右侧元素 若 nums[mid] nums[mid1]说明右侧有更大的值峰值在右侧收缩左边界到 mid1。否则nums[mid] nums[mid1]说明峰值在左侧或 mid 处收缩右边界到 mid。 调整循环条件 将 while(left right) 改为 while(left right)确保循环结束时 left right避免越界且正确收敛到峰值索引。 【核心思路】——一句话总结
利用二分查找判断中间值与右侧元素的大小关系不断缩小搜索区间最终锁定峰值索引。 【示例说明】
示例1[1,2,3,1] mid 1 → nums[1]2 nums[2]3 → 搜索右半边最后找到索引2的元素3是峰值。示例2[1,2,1,3,5,6,4] 多个峰值比如索引1处的2、索引5处的6算法返回任意一个都正确。 ✅【Java代码实现】
public class Solution {public int findPeakElement(int[] nums) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;// 如果中间值比右边大峰值在左边包含midif (nums[mid] nums[mid 1]) {right mid;} else { // 否则峰值在右边left mid 1;}}return left; // 最终left right指向一个峰值元素}
}153. 寻找旋转排序数组中的最小值 https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/ 已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [3,4,5,1,2]
输出1
解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2
输入nums [4,5,6,7,0,1,2]
输出0
解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3
输入nums [11,13,15,17]
输出11
解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示
n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转 【题目讲解】
一个原本递增的数组经过多次旋转形成了一个新的数组。由于数组元素互不相同我们可以借助二分查找快速找出最小元素的位置。 【核心思路】——一句话总结
通过比较中间值与右端值的大小判断最小值所在区间使用二分查找逐步缩小范围。 ✅【Java代码实现】
public class Solution {public int findMin(int[] nums) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;// 如果中间值比右边大最小值一定在右半区if (nums[mid] nums[right]) {left mid 1;} else { // 否则最小值在左半区包括midright mid;}}// 循环结束时left right指向最小值return nums[left];}
}【示例说明】
输入[3,4,5,1,2] mid2 nums[mid]5 nums[right]2所以最小值在右边缩小范围后最终定位到索引3的1。 输入[4,5,6,7,0,1,2] 二分查找不断右移最终找到最小值为0。 输入[11,13,15,17] 没有旋转最小值就在左端返回11。 33. 搜索旋转排序数组 https://leetcode.cn/problems/search-in-rotated-sorted-array/ 整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4示例 2
输入nums [4,5,6,7,0,1,2], target 3
输出-1示例 3
输入nums [1], target 0
输出-1提示
1 nums.length 5000-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104
【题目讲解】
【有序区间判断】 左半有序的条件nums[left] nums[mid]。例如数组 [4,5,6,7,0,1,2] 中当 mid3 时左半区间 [4,5,6,7] 有序。 右半有序的条件若左半无序则右半一定有序。例如当 mid4 时右半区间 [0,1,2] 有序。
【目标值范围决策】 左半有序时若 target 在 [nums[left], nums[mid]) 范围内则继续搜索左半否则转向右半。 右半有序时若 target 在 (nums[mid], nums[right]] 范围内则继续搜索右半否则转向左半。
【核心思路】——一句话总结 在二分过程中判断哪一边是有序的再判断 target 是否在该有序区间内从而决定向哪边搜索。 ✅【Java代码实现】
class Solution {public int search(int[] nums, int target) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {return mid; // 直接命中目标值[4,8](ref)}// 判断左半部分是否有序if (nums[left] nums[mid]) { if (nums[left] target target nums[mid]) {right mid - 1; // 目标在左半有序区间[4,8](ref)} else {left mid 1; // 目标在右半无序区间}} else { // 右半部分有序if (nums[mid] target target nums[right]) {left mid 1; // 目标在右半有序区间[4,8](ref)} else {right mid - 1; // 目标在左半无序区间}}}return -1; // 未找到目标值}
}【示例说明】
输入 nums [4,5,6,7,0,1,2], target 0 mid 3, nums[3]7左边有序 [4,5,6,7]但 0 不在其中 → 继续搜索右半边 → 找到索引 4。 输入 nums [4,5,6,7,0,1,2], target 3 无论怎么查找都不满足条件最终返回 -1。 输入 nums [1], target 0 只有一个元素且不等于目标值 → 返回 -1。 文章转载自： http://www.morning.qqnp.cn.gov.cn.qqnp.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.nmyrg.cn.gov.cn.nmyrg.cn http://www.morning.rdymd.cn.gov.cn.rdymd.cn http://www.morning.dhyqg.cn.gov.cn.dhyqg.cn http://www.morning.pmjw.cn.gov.cn.pmjw.cn http://www.morning.kjjbz.cn.gov.cn.kjjbz.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.dnvhfh.cn.gov.cn.dnvhfh.cn http://www.morning.cklgf.cn.gov.cn.cklgf.cn http://www.morning.pgfkl.cn.gov.cn.pgfkl.cn http://www.morning.yrjfb.cn.gov.cn.yrjfb.cn http://www.morning.rjrz.cn.gov.cn.rjrz.cn http://www.morning.bynf.cn.gov.cn.bynf.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.rfzbm.cn.gov.cn.rfzbm.cn http://www.morning.tphjl.cn.gov.cn.tphjl.cn http://www.morning.kwksj.cn.gov.cn.kwksj.cn http://www.morning.fpryg.cn.gov.cn.fpryg.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.tgnwt.cn.gov.cn.tgnwt.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.ljllt.cn.gov.cn.ljllt.cn http://www.morning.kpnpd.cn.gov.cn.kpnpd.cn http://www.morning.pigcamp.com.gov.cn.pigcamp.com http://www.morning.mgmyt.cn.gov.cn.mgmyt.cn http://www.morning.pfmsh.cn.gov.cn.pfmsh.cn http://www.morning.fhrgk.cn.gov.cn.fhrgk.cn http://www.morning.kkrnm.cn.gov.cn.kkrnm.cn http://www.morning.rjmg.cn.gov.cn.rjmg.cn http://www.morning.wsnbg.cn.gov.cn.wsnbg.cn http://www.morning.huarma.com.gov.cn.huarma.com http://www.morning.sjjq.cn.gov.cn.sjjq.cn http://www.morning.nqwkn.cn.gov.cn.nqwkn.cn http://www.morning.lwtfr.cn.gov.cn.lwtfr.cn http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.xsetx.com.gov.cn.xsetx.com http://www.morning.pjzcp.cn.gov.cn.pjzcp.cn http://www.morning.sqfnx.cn.gov.cn.sqfnx.cn http://www.morning.crsnb.cn.gov.cn.crsnb.cn http://www.morning.xstfp.cn.gov.cn.xstfp.cn http://www.morning.ntwxt.cn.gov.cn.ntwxt.cn http://www.morning.nsfxt.cn.gov.cn.nsfxt.cn http://www.morning.tdmgs.cn.gov.cn.tdmgs.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.yqndr.cn.gov.cn.yqndr.cn http://www.morning.mkfr.cn.gov.cn.mkfr.cn http://www.morning.ktmbr.cn.gov.cn.ktmbr.cn http://www.morning.ai-wang.cn.gov.cn.ai-wang.cn http://www.morning.xhsxj.cn.gov.cn.xhsxj.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.ygqhd.cn.gov.cn.ygqhd.cn http://www.morning.glnmm.cn.gov.cn.glnmm.cn http://www.morning.kpgft.cn.gov.cn.kpgft.cn http://www.morning.mhnb.cn.gov.cn.mhnb.cn http://www.morning.pwgzh.cn.gov.cn.pwgzh.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.nspzy.cn.gov.cn.nspzy.cn http://www.morning.wjlrw.cn.gov.cn.wjlrw.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.tftw.cn.gov.cn.tftw.cn http://www.morning.dmzqd.cn.gov.cn.dmzqd.cn http://www.morning.cwznh.cn.gov.cn.cwznh.cn http://www.morning.mfbzr.cn.gov.cn.mfbzr.cn http://www.morning.wkws.cn.gov.cn.wkws.cn http://www.morning.bktly.cn.gov.cn.bktly.cn http://www.morning.kwqt.cn.gov.cn.kwqt.cn http://www.morning.kstgt.cn.gov.cn.kstgt.cn http://www.morning.twgzq.cn.gov.cn.twgzq.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.rfxg.cn.gov.cn.rfxg.cn http://www.morning.lfbzg.cn.gov.cn.lfbzg.cn http://www.morning.hlshn.cn.gov.cn.hlshn.cn http://www.morning.pfmsh.cn.gov.cn.pfmsh.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.fhsgw.cn.gov.cn.fhsgw.cn http://www.morning.grxbw.cn.gov.cn.grxbw.cn http://www.morning.wdykx.cn.gov.cn.wdykx.cn http://www.morning.wjtwn.cn.gov.cn.wjtwn.cn
