秋招突击——7/10——复习{}——新作{在排序数组中查找元素的第一个最后一个位置、搜索旋转排序数组}

文章目录

- 引言
- 复习
- 新作
- - 在排序数组中查找元素的第一个和最后一个位置
  - - 个人实现
    - 参考实现
  - 搜索旋转排序数组
  - - 个人实现
    - 参考实现
- 总结

引言

复习

新作

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

题目链接

在这里插入图片描述
注意

非递减序列==》元素是递增或者相等，并不是严格递增的
找到给定目标值在数组中开始的位置和结束的位置
时间复杂度是logn

个人实现

这道题就是典型的二分查找的，但是需要知道你背的模板的特点的——“左加大，右减小”

class Solution {public int[] searchRange(int[] nums, int tar) {//define result vectorint[] res = {-1,-1};if(nums.length == 0)    return res;// binary findint m = nums.length;int l = 0,r = m - 1;while(l < r){int mid = (l + r) >> 1;if(nums[mid] >= tar) r = mid;else l = mid + 1;}// System.out.println(l);// judge whether find the valueif(nums[l] != tar)   return res;// the value is the first bigger numwhile(l >= 1 && nums[l - 1] == tar)  l --;while(r + 1 < m && nums[r + 1] == tar)  r++;res[0] = l;res[1] = r;return res;}
}

写是写完了，这里得去看一下Java中数组的操作，这里整的有点不熟悉，导致很多操作和C++弄混了！

// create the fixed length array
int[] fixedArray = new int[5];
int[] ifxedArray = {1,2,3,4,5};

参考实现

这里是使用了两个不同的模板，一个确定左边界，还有一个是确定有边界的。具体两个模板如下

确定左边界

int l = 0,r = m-1;
while(l < r){int mid = (r + l) >> 1;if(nums[mid] >= tar)	r = mid;else l = mid + 1;
}
// l is the left edge

确定右边界

int l = 0,r = m - 1;
while(l < r){int mid = (l + r + 1) >> 1;  // 仅仅针对右边界，防止死循环if(nums[mid] <= tar)	l = mid;else r = mid - 1;
}

最终实现如下

class Solution {public int[] searchRange(int[] nums, int tar) {//define result vectorint[] res = {-1,-1};if(nums.length == 0)    return res;// binary findint m = nums.length;int l = 0,r = m - 1;while(l < r){int mid = (l + r) >> 1;if(nums[mid] >= tar) r = mid;else l = mid + 1;}// judge whether find the valueif(nums[l] != tar)   return res;res[0] = l;// the value is the first bigger numl = l ;r = m - 1;while(l < r){int mid = (l + r + 1) >> 1;System.out.println(mid);if(nums[mid] <= tar)    l = mid;else r = mid - 1;}res[1] = r;return res;}
}

搜索旋转排序数组

题目链接

注意
数组严格单调递增
数组不为空
数组的值不会存在溢出的情况

个人实现

这道题是一个二分查找，但是需要转换坐标，将当前坐标转换为未旋转之前的坐标，或者是对其进行分段二分，然后查找目标值。
现在有一个问题，无论是哪种方法，都需要知道在哪里进行的反转，如果完整遍历一次对应元素，时间复杂度就是O（n），肯定超时，现在就是想着通过单调递增的方式，尽量快速确定反转的地方。
找到反转点
- 元素与元素之间只有严格的大于或者小于关系，往后遍历就是一定大于，往前遍历一定小于，异常就是说明旋转点，就在这一段
找到target就是使用二分查找

class Solution {public int binFind(int[] nums,int l,int r,int tar){while(l < r){int mid = (l + r) >> 1;if(nums[mid] >= tar) r = mid;else  l = mid + 1;}return l;}public int search(int[] nums, int tar) {int m = nums.length ;// handle the edge situationif(m == 1)  return nums[0] == tar?0:-1;// find the reverse pointint len = m / 2;int revP = 0;while(len > 1){if(nums[revP] < nums[revP + len - 1]){revP += len;}else{len /= 2;}}// find the target int res;System.out.println(revP);if(tar > nums[0]){res = binFind(nums,0,revP,tar);}else{System.out.println("last");res = binFind(nums,revP + 1 ,m - 1,tar);}System.out.println(res);// judge the result if(nums[res] == tar)    return res;else return -1;}
}

在这里插入图片描述
这里只能通过部分样例

因为第一个是总是能够算准的，但是第二个不好处理，不应该呀！第二个总是越界，出现各种各样的问题！
- 反转点在第一个元素的位置
- 反转点在最后一个元素的位置
- 仅有两个元素，如何进行判定

但是就是会出现异常！难受！

参考实现

这里整体的思路和我的一样，先找划分点，然后二分查找。

这里有一个很巧妙的地方，就是一开始根据条件确定旋转点，类似的二分都可以用同样的思路

基本想法和我的是一样的，都是通过等分对应区间长度，然后在进行比较划分，只不过他的套用模板，可靠性更高！

在这里插入图片描述

具体实现代码如下

class Solution {public int search(int[] nums, int tar) {int m = nums.length ;// handle the edge situationif(m == 1)  return nums[0] == tar?0:-1;// find the reverse pointint l = 0 ,r = m - 1;while(l < r){int mid = (l + r + 1) >> 1;if(nums[mid] >= nums[0]) l = mid;else  r = mid - 1;}// find the target if(tar >= nums[0] ){l= 0;}else{l = l + 1;r = m - 1; }while(l < r){int mid = (l + r) >> 1;if(nums[mid] >= tar) r = mid;else  l = mid + 1;}// judge the result if(nums[r] == tar)    return r;else return -1;}
}

对于模板的进一步总结
左加大返回右，右减小返回左

// 方案一，右边界
int l = 0,r = m - 1;
while(l < r){int mid = (r+l)>>1;if(nums[mid] >= tar)	r = mid;else l = mid + 1;
}
return r;// 方案二，左边界
int l = 0,r = m - 1;
while(l < r){int mid = (r+l)>>1;if(nums[mid] <= tar)	l = mid;else r = mid - 1;
}
return l;