旋转数组问题总结

标签：二分查找，翻转数组

        笔者在刷LeetCode时多次遇到旋转数组问题，将其各类问题加以总结，从简入深整理出关于旋转数组的全部问题题解思路和代码，希望对读者有所帮助

题目：189.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

输入: nums = [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:

输入：nums = [-1,-100,3,99], k = 2

输出：[3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]

思路：两次翻转数组 第一次整体翻转使原数组后k个元素位于前k个元素中，但内部顺序正好相反，所以还需要第二次翻转前k个元素 剩下的n-k个元素同理 即Reverse[0,n]; Reverse[0,k-1]; Reverse[k,n];

题解：

class Solution {
public:
    /*题解：较为巧妙的办法 两次翻转数组*/
    /*第一次翻转数组使前n-k个元素移动到后方,后k个元素翻转到前方但内部顺序正好相反*/
    /*所以再翻转[0,k-1] [k,n]后即可得到答案*/
    /*注意k大于n的情况*/
    void rotate(vector<int>& nums, int k) {
        k=k % nums.size();   //防止k>n越界
        int n = nums.size()-1;
        
        Reverse(nums, 0, n);
        Reverse(nums, 0, k-1);
        Reverse(nums, k , n);
    }
​
    /*负责翻转指定区间的数组元素*/
    void Reverse(vector<int>& nums , int start , int end)
    {
        while(start<end)
        {
            swap(nums[start++], nums[end--]);
        }
    }
};

题目2：153. 寻找旋转排序数组中的最小值

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 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 次得到输入数组。

思路：无重复元素 数组整体满足二分条件 分界点为nums[0],当mid位于左部有序区则向右移l=mid+1 同理 落入右部r=mid 最后逼近在r处取得右部有序区的边界值也就是数组的最小值，注意翻转0或n次单调的特殊情况。时间复杂度和二分一致O（Log2N）

题解：

class Solution {
public:
    /*无重复元素 左半有序区的值一定全>=nums[0]  右半有序区的值一定全<nums[0]
      采用二分查找左右有序区的分界点，右半有序区的分界点一定是最小的元素
      注意判特殊无翻转或翻转n次的单调情况，直接返回nums[0]*/
    int findMin(vector<int>& nums) {
        int n = nums.size()-1;
        //判特殊情况
        if(nums[0] < nums[n]) return nums[0];
        int l=0,r=n;
        while(l<r)
        {
            int mid = l+(r-l)/2;
            //若mid位于左部有序区 则需要向右找分界点，取等原因是nums[0]也包含在左部有序区 l=mid+1
            if(nums[mid]>=nums[0])
            {
                l=mid+1;
            }
            else r=mid;
            
        }
        return nums[r];
    }
};

154. 寻找旋转排序数组中的最小值 II

题目：

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [1,3,5] 输出：1

示例 2：

输入：nums = [2,2,2,0,1] 输出：0

思路：思路大体和上方一致，但初始数组不满足二分的严格部分单调，需要剔除末尾和开头重复的元素，后续二分一致，剔除过程时间复杂度为O(N) 后续二分O(Log2N) 所以总体时间复杂度为O(N)

题解：

class Solution {
public:
    /*有重复元素 左半有序区的值一定全>=nums[0] 右半有序区的值不一定全<nums[0]有可能会=nums[0]
      要采用二分法需要严格遵守部分单调，所以需要先剔除掉右半有序区结尾和nums[0]相等的重复的元素
      后续基本一致，采用二分查找左右有序区的分界点，右半有序区的分界点一定是最小的元素
      由于模板采用的是向下取整的mid 在r处取值返回的最小元素的索引一定是最小的
      注意判特殊单调的情况，剔除时注意边界判断*/
    int findMin(vector<int>& nums) {
        int n = nums.size()-1;
        //剔除结尾和nums[0]相等的重复元素,这步复杂度是O(N)
        while(n>0 && nums[n]==nums[0]) n--;
        //判特殊情况
        if(nums[0] < nums[n]) return nums[0];
        int l=0,r=n;
        while(l<r)
        {
            int mid = l+(r-l)/2;
            //若mid位于左部有序区 则需要向右找分界点，取等原因是nums[0]也包含在左部有序区 l=mid+1
            if(nums[mid]>=nums[0])
            {
                l=mid+1;
            }
            else r=mid;
            
        }
        return nums[r];
    }
};

题目：33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., 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 。

示例 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

思路：

旋转数组搜索问题,思路还是通过二分不断逼近求出target的索引,此问题无重复可直接二分

二分思路需要考虑所有情况

1、当nums[mid] == target时 无重复元素直接返回mid

2、当mid落入左半有序区时 即nums[mid]>=nums[0] 若nums[0] <= target <nums[mid]则落入 [l,mid)左部有序区 r=mid-1;

否则target将落入右部无序区(mid,n]   l=mid+1; (target<nums[0] || target>nums[mid])

3、当mid落入右半有序区时 即nums[mid]<nums[0] 若 nums[mid] < target < nums[0]则落入(mid,r]右部有序区 l=mid+1;

 否则target将落入左部无序区[0,mid) r=mid-1; (target >=nums[0] || target<nums[mid])

题解：

class Solution {
public:
    /*旋转数组搜索问题,思路还是通过二分不断逼近求出target的索引,此问题无重复可直接二分
      二分思路需要考虑所有情况
      当nums[mid] == target时 无重复元素直接返回mid
      当mid落入左半有序区时 即nums[mid]>=nums[0] 若nums[0] <= target <nums[mid]则落入[l,mid)左部有序区 r=mid-1;
                                                 否则target将落入右部无序区(mid,n] l=mid+1; (target<nums[0] || target>nums[mid])
      当mid落入右半有序区时 即nums[mid]<nums[0]  若 nums[mid] < target < nums[0]则落入(mid,r]右部有序区 l=mid+1;
                                                 否则target将落入左部无序区[0,mid) r=mid-1; (target >=nums[0] || target<nums[mid])
    */
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        
        int l=0,r=n-1;
        while(l<r)
        {
            int mid = l+(r-l)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid] >= nums[0])
            {
                if(target >=nums[0] && target<nums[mid]) r=mid-1;
                else l=mid+1;
                
            }
            else{
                if(target > nums[mid] && target < nums[0]) l=mid+1;
                else r=mid-1;
            }
        }
        if(nums[r] == target) return r;
        else return -1;
    }
};

题目：81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 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[0]相等的重复元素以满足而二分条件

题解：

class Solution {
public:
    /*
    在上题基础上多了重复元素 二分的前提需要剔除末尾与nums[0]相等的重复元素
    */
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        while(n>1 && nums[n-1] == nums[0]) n--; //多出的一步 记得判边界条件
        int l=0,r=n-1;
        while(l<r)
        {
            int mid = l+(r-l)/2;
            if(nums[mid]==target) return true;
            if(nums[mid] >= nums[0])
            {
                if(target >=nums[0] && target<nums[mid]) r=mid-1;
                else l=mid+1;
                
            }
            else{
                if(target > nums[mid] && target < nums[0]) l=mid+1;
                else r=mid-1;
            }
        }
        if(nums[r] == target) return true;
        else return false;
    }
​
};

题目：面试题 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]之间

思路：在上一题的基础上有目标值的情况下需要返回最小索引的目标值（受重复元素的影响）,由于采用向下取整的二分模板，返回的就是最小索引的重复元素目标值，改变一些返回条件即可。

题解：

class Solution {
public:
        /*
        在上题基础上 修改一些情况,改动点都加以注释 
        */
    int search(vector<int>& nums, int target) {
        
        int n = nums.size();
        while(n>1 && nums[n-1] == nums[0]) n--;
        int l=0,r=n-1;
        while(l<r)
        {
            int mid = l+(r-l)/2;
            //改动点：由于重复元素的存在还需要判断左侧是否还有相同元素更小的索引
            if(nums[mid]==target) r=mid;
            
            else if(nums[mid] >= nums[0])
            {
                if(target >=nums[0] && target<nums[mid]) r=mid-1;
                else l=mid+1;
                
            }
            else{
                if(target > nums[mid] && target < nums[0]) l=mid+1;
                else r=mid-1;
            }
        }
        if(nums[r] == target) return r;
        else return -1;
    }
};

        到此旋转数组问题就基本解决完啦，如果文中分析，题解代码有不足的地方欢迎大家在评论区讨论和指正。