概述
目录
1、LeetCode189. 旋转数组
1.1、暴力破解
1.2、环状替换
1.3、数组反转法
2、LeetCode33. 搜索旋转排序数组
3、LeetCode81. 搜索旋转排序数组 II
4、LeetCode面试题 10.03. 搜索旋转数组
4.1、搜索左侧边界
4.2、搜索右侧边界
5、寻找旋转有序数组的最值(无重复元素)
5.1、LeetCode153. 寻找旋转排序数组中的最小值
5.2、寻找旋转有序数组的最大值
6、寻找旋转排序数组中的最值 II（存在重复值）
6.1、LeetCode154. 寻找旋转排序数组中的最小值 II
6.2、寻找旋转排序数组中的最大值 Ⅱ
1、LeetCode189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]说明:
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的 原地 算法。
1.1、暴力破解
每次向右移动一次，移动 k 次即可，代码略。
1.2、环状替换
思路：直接将元素放入旋转之后的最终位置。
编程步骤：
1、保存当前索引的元素值curVal和索引值curIndex
2、计算下一个节点位置索引nxtIndex,并保存nxtVal
3、用当前curVal更新nums[nxtIndex]。
4、更新curVal值和当前索引curIndex。
5、更新后判断 curIndex 是否已经回到起点，没有则继续到下一个位置，回到起点停止本轮环状替换，继续起点处的下一个节点 的替换
6、本算法的每个元素都需要移动一次，当元素的替换次数cnt等于nums.length时，数组旋转完成。
核心：
在于定义两个变量curVal，nxtVal时刻保存当前位置元素和下一个位置元素，实时更新索引，用nxtVal实时更新curVal。
public void rightRotate(int[] nums, int k) {
if(nums == null || nums.length <= 1){
return ;
}
k %= nums.length;
if(k == 0){
return ;
}
int cnt = 0;
for(int i = 0; i < nums.length && cnt < nums.length; i++){
int curVal = nums[i];
int curIndex = i;
do{
cnt++;
int nxtIndex = (curIndex+k)% nums.length;
int nxtVal = nums[nxtIndex];
nums[nxtIndex] = curVal;
curVal = nxtVal;
curIndex = nxtIndex；
}while(curIndex != i);
}
}1.3、数组反转法
这个方法基于这个事实：当我们旋转数组 k 次， k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n−k 个元素，就能得到想要的结果。假设 n=7 且 k=3 。
原始数组 : 1 2 3 4 5 6 7
反转所有数字后 : 7 6 5 4 3 2 1
反转前 k 个数字后 : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果
代码略
2、LeetCode33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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二分搜索思路：
1、有序数组经旋转多次有还是能保证左、右两侧至少有一侧是有序的(重点)
2、判断左侧有序还是右侧有序
3、计算中点是否为target，为目标值即返回，否则继续
4、在有序的一侧进行target查找,根据有序数组的性质可以很轻松判断target是否在范围内
即>= nums[min] && <=nums[max]，注意已经排除了中点值nums[mid] != target。
5、注意需要获取 nums[right] 的值判断 target 的范围，所以初始值取 nums.length -1。
此时数组的的搜索范围为[0,nums.length-1)，因此，当循环结束时还需要判断left为nums.length-1,
如果是还需要继续判断是否为目标值。
public int search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0,right = nums.length -1;
while(left < right){
int mid = left + (right-left)/2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] > nums[left]){//左侧有序
if(target >= nums[left] && target < nums[mid]){
right = mid;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[left]){//右侧有序
if(target > nums[mid] && target <= nums[right]){
left = mid+1;
}else{
right = mid;
}
}else{//mid和left重合,mid又不等于target
left = mid + 1;
}
}
/*if(left == nums.length -1){
return nums[left] == target? left:-1;
}else{
return -1;
}*/
//如果left不等于nums.length-1,则肯定有nums[left] != target
return nums[left] == target ? left:-1;
}3、LeetCode81. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
思路：
1、和LeetCode33区别的是数组中存在重复值,当nums[mid] == nums[left],可能遭遇到重复值时
只能线性排除无法使用二分法。
public boolean search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return false;
}
int left = 0,right = nums.length -1;
while(left < right){
int mid = left + (right-left)/2;
if(nums[mid] == target){
return true;
}
if(nums[mid] > nums[left]){//左侧有序
if(target >= nums[left] && target < nums[mid]){
right = mid;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[left]){//右侧有序
if(target > nums[mid] && target <= nums[right]){
left = mid+1;
}else{
right = mid;
}
}else{//mid和left重合,或者遇到重复值,mid又不等于target
left++;//线性排除
}
}
/*if(left == nums.length -1){
return nums[left] == target? left:-1;
}else{
return -1;
}*/
//如果left不等于nums.length-1,则肯定有nums[left] != target
return nums[left] == target ? true:false;
}4、LeetCode面试题 10.03. 搜索旋转数组
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
示例2:
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）
提示: arr 长度范围在[1, 1000000]之间
思路：
1、LeetCode81的区别的是数组中存在重复值,需要判断当nums[mid] == nums[left],可能遭遇到重复值，此时需要判断是否为 target 如果是则返回left，否则线性排除。
2、和LeetCode33的区别是当搜索到 target 时不在立刻返回，而是收缩右侧边界right = mid。因为上文逻辑并未判断 nums[mid]是否为target,因此在判断是否在左侧区间有nums[mid] <= target。
3、当右侧区域为升序时还是要优先判断目标值是否在左侧区域，此时数组的断崖处(最大最小值)在左侧,因此有target >= nums[left] 或者 target <= nums[mid]
4.1、搜索左侧边界
public int searchLeftRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0,right = nums.length -1;
while(left < right){
int mid = left + (right-left)/2;
if(nums[mid] > nums[left]){//左侧有序
if(target >= nums[left] && target <= nums[mid]){
right = mid;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[left]){//右侧有序
if(target >= nums[left] || target <= nums[mid]){
right = mid;
}else{
left = mid + 1;
}
}else{//mid和left重合,mid又不等于target
if(nums[left] == target){
return left;
}else{
left++;
}
}
}
//如果left不等于nums.length-1,则肯定有nums[left] != target
return nums[left] == target ? left:-1;
}4.2、搜索右侧边界
思路：
1、和搜索左侧边界不同是当设定起始搜索区间为[0,nums.length-1)时，缺少一个nums.length-1并未搜索
2、和LeetCode34搜正常搜索右侧边界一样,当left=0时即没有搜索到target除此之外，在区间[0,nums.length-1)内搜索到 target，left=mid+1。
public int searchRightRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0,right = nums.length -1;
while(left < right){
int mid = left + (right-left)/2;
if(nums[mid] > nums[right]){//左侧有序
if(target >= nums[mid] || target <= nums[right]){
left = mid + 1;
}else{
right = mid;
}
}else if(nums[mid] < nums[right]){//右侧有序
if(target >= nums[mid] && target <= nums[right]){
left = mid + 1;//nums[mid] == target,向左收缩窗口且形式left= mid+1;
}else{
right = mid;
}
}else{//mid和right存在重复值。
if(nums[right] == target){
return right;
}else{
right--;
}
}
}
if(left > 0 && left < nums.length -1){//nums.length-1尚未搜索
left--;//根据收缩形式left=mid+1。
}
return nums[left] == target ? left:-1;
}5、寻找旋转有序数组的最值(无重复元素)
5.1、LeetCode153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0思路：
1、首先判断有序数组是发生旋转，若未发生旋转直接返回left，继续判断旋转数组哪一侧为有序数组，需要取出nums[right]的计 算范围，初始搜索区间仍然为[0,nums.legth-1)。不妨碍最后结果输出 left 的取值范围。
2、若nums[mid] > nums[left]，则左侧为有序数组
2.1、若nums[mid] <= nums[right]则表示右侧也为有序数组，直接返回left
说明：由于数组中没有重复元素，因此nums[mid] == nums[right] 永远不会成立
2.2、若nums[mid] > nums[right]，则说明右侧存在断崖(最大最小值)，更新左侧边界left = mid+1；
3、若nums[mid] < nums[left],则说明右侧升序，左侧存在断崖，此时极小值肯定在左侧，更新右侧边界right = mid；
4、 若nums[mid] == nums[left]，则说明 mid 和 left 重合，此时 right = left+1，取出最小值即可。
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MAX_VALUE;
}
int left =0,right = nums.length -1;
if (nums[right] >= nums[left]) {//数组并未旋转
return nums[left];
}
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] > nums[left]){
if(nums[mid] <= nums[right]){
return nums[left];
}else{//右侧存在断崖
left = mid + 1;
}
}else if(nums[mid] < nums[left]){
right = mid;
}else{//mid 和 left重合,此时right = left+1。
return Math.min(nums[left],nums[right]);
}
}
return nums[left];
}5.2、寻找旋转有序数组的最大值
思路：和搜索最小值不同的是，更新左侧边界的是有条件的，当nums[mid] > nums[right]时，左侧有序，右侧存在断崖， 最大值 肯定存在断崖处，如[2,3,1]，同时需要判断 mid 是否为断崖峰值，由于 right > mid 恒成立，因此可以利用 mid 和 mid+1 值的大小来判断。
public int findMax(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MIN_VALUE;
}
int left =0,right = nums.length -1;
if (nums[right] >= nums[left]) {//数组并未旋转
return nums[right];
}
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] < nums[right]){
if(nums[mid] >= nums[left]){
return nums[right];
}else{//左侧存在断崖
right = mid;
}
}else if(nums[mid] > nums[right]){//右侧存在断崖
if(nums[mid] < nums[mid+1]){//mid永远不会和right重合因此mid+1不会越界
left = mid + 1;
}else{//断崖正好在mid
//right = mid;
return nums[mid];
}
}else{//不存在
return Integer.MIN_VALUE;
}
}
return nums[left];
}6、寻找旋转排序数组中的最值 II（存在重复值）
6.1、LeetCode154. 寻找旋转排序数组中的最小值 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。注意数组中可能存在重复的元素。
思路：和搜索不带重复值得差异是：mid 和 left 重合返回极小值，没有重合仅仅是遭遇到重复值线性消除即可
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MAX_VALUE;
}
int left =0,right = nums.length -1;
if(nums[right] > nums[left]){
return nums[left];
}
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] > nums[left]){
if(nums[mid] <= nums[right]){
return nums[left];
}else{//右侧存在断崖
left = mid + 1;
}
}else if(nums[mid] < nums[left]){//左侧存在断崖
right = mid;
}else{//mid 和 left重合(此时right = left+1),或者遭遇重复值
if(left == mid){
return Math.min(nums[left],nums[right]);
}else{
left++;
}
}
}
return nums[left];
}6.2、寻找旋转排序数组中的最大值 Ⅱ
思路：
1、和搜索不带重复值的最大值的区别在于，当nums[mid] == nums[right]，即遭遇到了重复值，线性消除即可。
2、由于存在重复值因此判mid是断崖峰值的条件，必须是nums[mid]>nums[mid+1]，当nums[mid] == nums[mid+1]存在重复值， 更新左侧窗口
public int findMax(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MIN_VALUE;
}
int left =0,right = nums.length -1;
if (nums[right] > nums[left]) {//数组并未旋转
return nums[right];
}
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] < nums[right]){
if(nums[mid] >= nums[left]){
return nums[right];
}else{//左侧存在断崖
right = mid;
}
}else if(nums[mid] > nums[right]){//右侧存在断崖
if(nums[mid] <= nums[mid+1]){//mid永远不会和right重合因此mid+1不会越界
left = mid + 1;//遭遇重复值更新left和不存在重复值场景差别之一
}else{//断崖正好在mid
//right = mid;
return nums[mid];
}
}else{//遭遇重复值，线性消除
right--;
}
}
return nums[left];
}最后
以上就是多情豌豆为你收集整理的再次认识二分查找之搜索旋转数组1、LeetCode189. 旋转数组2、LeetCode33. 搜索旋转排序数组3、LeetCode81. 搜索旋转排序数组 II4、LeetCode面试题 10.03. 搜索旋转数组5、寻找旋转有序数组的最值(无重复元素)6、寻找旋转排序数组中的最值 II（存在重复值）的全部内容，希望文章能够帮你解决再次认识二分查找之搜索旋转数组1、LeetCode189. 旋转数组2、LeetCode33. 搜索旋转排序数组3、LeetCode81. 搜索旋转排序数组 II4、LeetCode面试题 10.03. 搜索旋转数组5、寻找旋转有序数组的最值(无重复元素)6、寻找旋转排序数组中的最值 II（存在重复值）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复