LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置


前言

国庆前最后一次打卡,国庆后继续开启,公众号bigsai回复进群欢迎加入打卡,如有帮助记得点赞收藏。

近期打卡记录:
LeetCode 32最长有效括号(困难) (本周)
LeetCode 30串联所有单词的子串&31下一个排列(上周)
LeetCode 27移除元素&28实现strStr()&29两数相除(上周)

二分查找我想大家都很熟悉,二分查找每次判断并比较元素所在区间进行压缩,每次都可以压缩一半的区间,所以压到1个大小把它你想来看就是(最坏)扩散了n次到达原始长度。

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

很多题就是原始的二分,但很多题就是二分变种。

33搜索旋转排序数组

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

这题其实就是一个二分变种,加了一些其他的条件。每次的mid要根据判断如何移动.一个正常序列分成左右两个序列,并且都是递增的,没有相同的。

就拿中间mid的值大于target就有以下几种情况:
LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
按照这样思路同理分析另一半一直求解即可。

ac代码为:

 public int search(int[] nums, int target) {
if(nums[0]==target)return 0;
if(nums[nums.length-1]==target)return nums.length-1;
int l=0;int r=nums.length-1;
while (l<r) {
int mid=(l+r)/2;
//System.out.println(mid+" "+l+" "+r);
if(nums[mid]==target)return mid;
// 8 9 2 3 4 5 6 7
if(nums[mid]>target)//中间大于目标值
{
if(nums[0]>target) {//最左侧都大于 只可能在右侧最小区域

if(nums[mid]<nums[0])//当前在右区域
{
r=mid;
}
else {
l=mid+1;
}
}
else {最左侧小于目标值 向左
r=mid;
}

}
// 8 9 2 3 4 5 6 7
else {//中间小于目标值
//如果在右侧区域往左
if(nums[nums.length-1]<target)//最右侧小于target 需要向左侧去
{
if(nums[mid]<nums[nums.length-1])//当前
{
r=mid;
}
else {
l=mid+1;
}

}
else //最右侧大于target 在小的区域内
{
l=mid+1;
}
//System.out.println(1);

}
}

return -1;
}

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

34在排序数组中查找元素的第一个和最后一个位置

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
入门二分,注意找到一个值后进行左右方向寻找边界问题。ac代码为:

 public int[] searchRange(int[] nums, int target) {
int a[]= {-1,-1};
if(nums.length==1&&nums[0]==target) {a[0]=0;a[1]=0;return a;}
if(nums.length==0)return a;
int leftindex,rightindex;
int left=0,right=nums.length-1;
while (left<right) {
//System.out.println(left+" "+right);
int mid=(left+right)/2;
if(nums[mid]==target)
{
leftindex=mid;
rightindex=mid;
while (leftindex>=0&&nums[leftindex]==target) {leftindex--;}
while (rightindex<nums.length&&nums[rightindex]==target) {rightindex++;}
a[0]=leftindex+1;a[1]=rightindex-1;
return a;
}
else if (nums[mid]<target) {
left=mid+1;
}
else {
right=mid;
}
}
if(nums[left]==target)
{
a[0]=left;a[1]=left;
}
return a;
}

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

35搜索插入位置

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
这题需要注意的就是插入位置或者查找到的编号。经典二分不多说你懂的/

 public int searchInsert(int[] nums, int target) {
if(nums[0]>=target)return 0;//剪枝
if(nums[nums.length-1]==target)return nums.length-1;//剪枝
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1;
while (left<right) {
int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if (nums[mid]>target) {
right=mid;
}
else {
left=mid+1;
}
}
return left;
}

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
本次打卡结束拉,下周国庆暂停一次(就一次)。欢迎其他小哥哥小姐姐加入打卡,微信搜索bigsai,回复进群加入打卡力扣!
LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置


Big sai

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
CSDN认证博客专家


scikit-learn

关注微信公众号:bigsai,回复进群即可加入leetcode打卡群,回复bigsai获取珍藏pdf一份。江科大本,南理研一。平凡的日子里努力充实自己,努力学习,努力分享。期待你的关注!

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode (二分小专题)33搜索旋转排序数组&34在排序数组中查找元素的第一个和最后一个位置&35搜索插入位置
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏