【算法】旋转数列
2024-04-22 23:00:46 #算法

基本描述

这东西和动态规划一样令人作呕。

旋转数列一般为旋转排序数列(Rotated Sorted Array)，和它有关的问题有很多，比如Leetcode153. Find Minimum in Rotated Sorted Array、Leetcode33. Search in Rotated Sorted Array。

旋转数列的定义为，对于给定数列$a_1,a_2,\cdots,a_n$，其以$k,k\in[1,n]$为中心旋转得到的数列为$a_k,a_{k+1},\cdots,a_{k-1}$。

这种数列，记作$num$，有这样几条性质：

  1. 最左端元素大于最右端元素，即$num[left] \geq num[right]$。

  2. $num$可沿着分界点$a_n$分为两个排序的数列，$a_k,a_{k+1},\cdots,a_n$和$a_1,a_2,\cdots,a_{k-1}。$

几乎所有问题都围绕这两条性质展开，我将讨论比较有代表性的几个问题。

无重复值：分界点的确定

该问题等价于寻找$a_n$，也等价于在旋转数列中寻找最大值/最小值的问题。

根据上面的第二条性质，可以发现，分界点处的值为左半数列最大值，其右侧的值为右半数列最小值。那么，这个问题可以很简单地通过二分搜索求解，判断中间值是否小于右指针处的值即可，分类讨论二者关系：

  1. 若大于，则表明中间值目前处于左半数列，需要让左端指针右移。
  2. 若小于，则表明其处于右半数列中，需要右端指针左移，但不能移动到mid-1，否则会导致搜索范围完全落在左半数列，无法求出正确的解。
  3. 若二者相等，则表明左右端指针都必然指向同一位置，实际上表明搜索其实已经结束了，此时可以选择让左指针右移跳出循环，也可以选择直接返回。

根据循环条件，退出循环时，左指针必然大于右指针，指向的是右侧数列的第二个元素或nums.size()，而右侧指针指向右侧数列的第一个元素，也就是旋转数列的最小值。

于是，我们可以解出Leetcode153. Find Minimum in Rotated Sorted Array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] >= nums[r]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[r];
    }
};

为什么不和左指针的值比较呢？因为当数列不旋转时，左半数列并不存在；而不论如何右半数列必然存在。和左侧指针的值作比较，很有可能出bug，解法也不如上面的方法优雅简单。

有重复值：分界点的确定

这种状况对应Leetcode154. Find Minimum in Rotated Sorted Array II。

我自己的解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] > nums[r]) {
                l = mid + 1;
            } else if(nums[mid] < nums[r]){
                r = mid;
            } else {
                r--;
            }
        }
        return nums[l];
    }
};

基本思想为，碰到重复的，就逐步缩小搜索区域。

Prev
2024-04-22 23:00:46 #算法
Next