# 搜索旋转排序数组

leetcode题号33

## 题目

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

```输入: nums = [4,5,6,7,0,1,2], target = 0

```输入: nums = [4,5,6,7,0,1,2], target = 3

## 解答

```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] )。

```输入: [3,4,5,1,2]

```输入: [4,5,6,7,0,1,2]

## 解答

```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;
}
};```

# 旋转数组

## 解答

```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;
}
}
}
};```

```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());
}
};```

# 搜索旋转排序数组 II

## 题目

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

```输入: nums = [2,5,6,0,0,1,2], target = 0

```输入: nums = [2,5,6,0,0,1,2], target = 3

## 解答

```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;```

# 寻找旋转排序数组中的最小值 II

## 题目

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

```输入: [1,3,5]

```输入: [2,2,2,0,1]

## 解答

```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.

## 题目

```输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5

```输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11

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;
}```

0 条评论

• ### 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

• ### 子序列问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• ### 【leetcode刷题】20T39-颜色分类

https://leetcode-cn.com/problems/sort-color

• ### LeetCode 75. 颜色分类（双指针）

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

• ### LeetCode 215. 数组中的第K个最大元素（快速排序）

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

• ### 哈希表：解决了两数之和，那么能解决三数之和么？

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三...