网站首页 文章专栏 旋转排序的数组
leetcode题号33
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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
关键的地方在于如果修改现有的二分查找，使之满足旋转排序数组的情况。
二分查找一般是target与nums[mid]作比较，我们也可以将[0-mid]视为左半数组，(mid, end())视为右半数组。显然必定有一个半数组是排序的，而另外一个不是。
可以用nums[left]， 与nums[mid]作比较，如果是小于等于，那么左半数组一定是排序的。因为如果不是，那么重新开始的值会是数组中最小的，并且小于nums[left], 因为这个是旋转排序。
接下来只需要在排序的半数组中查找，不满足要求的分到另一半数组。
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; if(nums.size() == 1){ if(target == nums[0]) return 0; else return -1; } while(left <= right){ int mid = (left + right) / 2; if(nums[mid] == target) return mid; if(nums[left] <= nums[mid]){ // 左半段为完全升序 if(target < nums[mid] && target >= nums[left]){ right = mid - 1; }else{ left = mid + 1; } }else{ // 右半段为完全升序 if(target > nums[mid] && target <= nums[right]){ left = mid + 1; }else{ right = mid - 1; } } } return -1; } };
leetcode题号 153
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2] 输出: 1
示例 2:
输入: [4,5,6,7,0,1,2] 输出: 0
基本思想是判断左半数组与右半数组哪个是有序的，然后朝非有序方向前进。一旦发现整个left到right是有序的，说明此时的nums[left]是最小值。
注意在向左前进时，right = mid, 而不是right = mid - 1, 否则容易错过最小点。
class Solution { public: int findMin(vector<int>& nums) { int left = 0, right = nums.size() - 1; int res; while(left <= right){ int mid = (left + right) / 2; if(nums[left] <= nums[mid] && nums[mid] <= nums[right]){ res = nums[left]; break; }else if(nums[left] <= nums[mid]){ // 左边是排序的 left = mid + 1; }else{ // 右边是排序的 // 要额外注意，左半数组是[0...mid], 右半数组是(mid, end()) // 如果这里是mid - 1，容易将最小的数绕过去 right = mid; } } return res; } };
一个错误的答案。 本来是想形成一个链式反应，一下子用O(1)的空间复杂度与O(n)的时间复杂度完成，可惜会有特殊情况，如[1,2,3,4], k = 2. nums[0] 与 nums[2]首尾相连，无法按预期运行。
class Solution { public: void rotate(vector<int>& nums, int k) { // 已知坐标i，求挪动后，哪个坐标的数会挪动到i，i的数又会挪动到哪里 // nums[(size + i - k) % size] -> nums[i] -> nums[(i + k) % size] int temp = nums[0]; for(int now_index = 0; ;){ int last_index = (nums.size() + now_index - k) % nums.size(); nums[now_index] = last_index != 0 ? nums[last_index] : temp; now_index = last_index; if(last_index == 0) return; } } };
后来又改为朴素的挪动方法，结果超时。
class Solution { public: void rotate(vector<int>& nums, int k) { int temp; k = k % nums.size(); if(k <= nums.size() / 2){ // 挪动较小，可以从左向右挪 for(int j = 0; j < k; j++){ temp = nums[nums.size() - 1]; for(int i = (int)nums.size() - 2; i >= 0; i--) nums[i + 1] = nums[i]; nums[0] = temp; } }else{ // 挪动较大，从右往左挪 for(int j = 0; j < (int)nums.size() - k; j++){ temp = nums[0]; for(int i = 0; i < nums.size() - 1; i++) nums[i] = nums[i + 1]; nums[nums.size() - 1] = temp; } } } };
下面为找的参考答案。
此题可以采用头插法，一个一个的移动。但是有种更加简单的选择数组的方式。我们可以采用翻转的方式，比如12345经过翻转就变成了54321，这样已经做到了把前面的数字放到后面去，但是还没有完全达到我们的要求，比如，我们只需要把12放在后面去，目标数组就是34512，与54321对比发现我们就只需要在把分界线前后数组再进行翻转一次就可得到目标数组了。所以此题只需要采取三次翻转的方式就可以得到目标数组，首先翻转分界线前后数组，再整体翻转一次即可。此题面试常考，大家可以记一下此方法。
class Solution { public: void rotate(vector<int>& nums, int k) { if(nums.size() <= 1) return; k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin() + k, nums.end()); } };
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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 可能包含重复元素。 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
主要是有重复数字后，left、right值可能与mid相等，导致无法判断哪半数组是有序的。本解法增加了在相等时的操作，即跳过该数，left++，right--。
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; if(nums.size() == 1){ if(target == nums[0]) return true; else return false; } while(left <= right){ int mid = (left + right) / 2; if(nums[mid] == target) return true; if(nums[left] < nums[mid]){ // 左半段为完全升序 if(target < nums[mid] && target >= nums[left]){ right = mid - 1; }else{ left = mid + 1; } }else if(nums[right] > nums[mid]){ // 右半段为完全升序 if(target > nums[mid] && target <= nums[right]){ left = mid + 1; }else{ right = mid - 1; } }else{ // 要么左边与mid相等，要么右边与mid相等 if(nums[left] == nums[mid]) left++; else right--; } } return false; } };
还可以在开始判断哪半数组有序前去重，
//处理重复数字 while(l<r&&nums[l]==nums[l+1]) ++l; while(l<r&&nums[r]==nums[r-1]) --r;
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5] 输出: 1
示例 2：
输入: [2,2,2,0,1] 输出: 0
说明：
这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
由于需要判断left-right之间是否是完全有序的，重复数字会影响判断。所以本解法先去重。
class Solution { public: int findMin(vector<int>& nums) { int left = 0, right = nums.size() - 1; int res; if(nums.size() == 1){ return nums[0]; } while(left <= right){ while(left < right && nums[left] == nums[left + 1]) left++; while(left < right && nums[right] == nums[right - 1]) right--; int mid = (left + right) / 2; if(nums[left] <= nums[mid] && nums[right] >= nums[mid] ){ res = nums[left]; break; } if(nums[left] <= nums[mid]){ left = mid + 1; }else{ right = mid; } } return res; } };
leetcode题号：面试题 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]之间
注意特殊用例
[5,5,5,1,2,3,4,5] 5
返回
0
不仅要考虑紧邻左侧相等，还要考虑右侧跨数组首尾端的相等。
相比于其他解法，新增的内容：
if(nums[mid] == target){ if(nums[mid] == nums[0]) return 0; while(mid > 0 && nums[mid] == nums[mid - 1]) mid--; return mid; }