什么是旋转数组?
旋转数组是一类特殊的数组, 旋转数组的特点是: 以旋转点作为界限, 两边的区间仍然保持单调的性质; 有时候我们遇到的不是全局性的单调性问题, 更多是一个局部单调性问题; 这里需要额外判断一些条件之后, 然后在用二分处理问题.
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 。你必须设计一个时间复杂度为 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
示例 3：输入：nums = [1], target = 0 输出：-1
分析:
1.旋转数组的特点是: 以旋转点作为界限, 两边的区间仍然保持单调的性质, 比如 [4,5,6,7,0,1,2] 和 [6,7,0,1,2,3,4]; 但是以搜索点作为界限: 左右两边的区间只存在一边必然单调, 一边可能不单调的性质; 在搜索的时候, 我们先判断以 nums[mid] 的一遍是否存在单调性, 比如我们去判断 nums[mid] 的右边是否存在单调性: 判断右边是否存在单调性的依据是最右边的元素是否大于当前元素, 如果是最最右侧的元素是更大的, 说明旋转点不在右边, 右边是单调的; 如果右边存在单调性, 我们再判断在 target 是否在右边的区间里面, 也就是增加判断 target 是介于 nums[mid] 和 nums[r]之间的值, 如果是那么就很方便地进行二分搜索; 如果不存在在右边边界, 那么只要递归地搜索左边的区间, 右边不需要再投入考虑
2.旋转数组的二分搜索相对与普通的二分搜索相当于多加了两层判断, 一层判断是当前搜索区间是否单调, 以及再判断当前元素是否再里面
3.旋转数组的二分搜索如果进入一个不单调的区间里面搜索, 该子问题的结构和原问题的结构是完全相同的, 继续递归的去搜索一个子数组, 这个数组也是一个旋转数组, 直到两边不再有任何旋转数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size()-1;
while (l <= r) {
int mid = l + (r - l) / 2;
int midNum = nums[mid];
if (midNum == target) {
return mid;
}
// 判断一侧是否是单调的: 例如判断右边如果是单调的
if (nums[mid] < nums[r]) {
// 判断 target 是否在右边区间
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
// 不在就去左边区间搜索
} else {
r = mid - 1;
}
// 判断另一侧左边的单调性也已知了, 因为旋转数组必然一边单调一边不单调
} else {
// 判断 target 是否在左边区间
if (nums[mid] > target && target >= nums[l]) {
r = mid - 1;
// 不在就去右边区间搜索
} else {
l = mid + 1;
}
}
}
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
分析:
1.这题相比元素无重复的情况, 多了一个可重复条件使得两边区间的有序性判断会失效; 举个例子是 [3,1,2,3,3,3,3], target = 2, 左边右边都无法判断单调性, 此时 nums[l] == nums[mid] == nums[r]; 遇到这种情况两边同时缩减一下范围: —l && —r, 然后继续执行旋转数组二分搜索
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return true;
// 如果出现了两边区间都没法判断的特殊情况: 两头缩减
} else if (nums[mid] == nums[l] && nums[mid] == nums[r]) {
++l;
--r;
// 左边区间单调
} else if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
// 或者右边区间单调
} else {
if (nums[r] >= target && target > nums[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return false;
}
};
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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 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 次得到输入数组。
分析:
1.旋转数组满足中点二分之后, 一边单调, 一边不单调的性质
2.我们二分搜一次, 可以找到一边的单调区间, 更新当前的最小值为单调区间的最左侧; 然后再去另一个不单调的区间里面去尝试找更小的元素, 直到两边都是单调的情况, 不断迭代找到整个数组的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = INT_MAX;
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
// 左边单调
if (nums[l] <= nums[mid]) {
ans = min(ans, nums[l]);
l = mid + 1;
// 如果右边单调
} else {
ans = min(ans, nums[mid]);
r = mid - 1;
}
}
return ans;
}
};
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
分析:
1.数组中存在了重复元素, 最小值仍然是依靠比较搜索区间最左边的元素 nums[l] 和 mid元素 nums[mid] 的大小关系分情况讨论去持续搜索
2.我们需要在搜索中处理掉 nums[l] == nums[mid] 这种情况, 同时处理掉 nums[r] == nums[mid] 的情况
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[mid+1]) {
return nums[mid+1];
}
while (nums[l] == nums[mid] && l < mid) ++l;
while (nums[r] == nums[mid] && mid < r) --r;
// 如果左边不是单调的, 去左边搜索
if (nums[l] > nums[mid]) {
r = mid;
} else if (nums[r] < nums[mid]) {
l = mid;
} else {
return nums[l];
}
}
return nums[l];
}
};
转载请注明来源, from goldandrabbit.github.io
