旋转数组求最小值

悠悠 2022-07-12 06:26 163阅读 0赞

旋转数组的概念就是对有序数组循环向右移动K位得到的数组。  
例如\[1,2,3,4,5\]经过右移2位后旋转后得到：\[4,5,1,2,3\]

## 一、如何得到旋转数组 ##

比如说现在要求旋转右移K位，求移动后的结果。

第一步要对K进行处理，因为假设原数组是\[1,2,3\]：  
当K=1，旋转数组为\[3,1,2\]  
当K=2，旋转数组为\[2,3,1\]  
当K=3，旋转数组为\[1,2,3\]  
当K=4，旋转数组为\[3,1,2\]  
…  
也就是说，当得到K时，先用K对n取模，n是数组大小。  
然后就是旋转操作，这里其实不需要借助辅助空间，伪代码如下：  
（1）逆置数组的前n-K个元素。  
（2）逆置数组的后K个元素。  
（3）逆置整个数组。  
举个例子数组\[1,2,3,4,5\] K=2 结果是\[4,5,1,2,3\]。

按照上面的步骤得到中间结果分别是：  
（1）\[3,2,1,4,5\]  
（2）\[3,2,1,5,4\]  
（3）\[4,5,1,2,3\]  
得到所求。

--------------------

## 二、不含重复值的情况 ##

由于原数组是有序的，经过右移得到2个升序的子序列，两个子序列的分界点刚好就是原序列中的最大和最小值，因此可以利用二分查找的某些性质。

class Solution {
    public:
        int findMin(vector<int>& nums) {
            int low = 0;
            int high = nums.size()-1;
            int mid;
            while(low < high)
            {
                mid = (low + high)/2;
                if(nums[mid]>nums[high])
                {
                    low=mid+1;
                }
                else if(nums[mid] < nums[high])
                {
                    high=mid;
                }
            }
            return nums[low];
        }
    };

--------------------

## 三、含重复值的情况 ##

如果原序列中含有重复的元素，譬如\[1,2,2,3,4\]，那么旋转之后依然含有重复元素，STL排序再去重的操作在这个地方没有必要，依然是利用二分查找的思想，跟上面类似，不过，当比较元素相等时，挪动一下索引，再进入下次计算。

class Solution {
    public:
        int findMin(vector<int>& nums) {
            int low=0;
            int high=nums.size()-1;
            int mid;
            while(low < high)
            {
                mid = (low+high)/2;
                if(nums[mid]>nums[high])
                {
                    low=mid+1;
                }
                else if(nums[mid]<nums[high])
                {
                    high=mid;
                }
                else
                {
                    --high;
                }
            }
            return nums[low];
        }
    };