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

基本描述

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

旋转数列一般为旋转排序数列(Rotated Sorted Array),和它有关的问题有很多,比如Leetcode153. Find Minimum in Rotated Sorted ArrayLeetcode33. 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