1.旋转数组（189 - 中）
题目描述：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。进阶：
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 :
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]
思路：多解法，其中使用额外数组，空间复杂度O(N)，其余O(1)。
- 使用额外数组：遍历原数组，将原数组下标为 ii 的元素放至新数组下标为 (i+k)%n 的位置，最后将新数组拷贝至原数组即可。
- 模拟循环：用一个变量tmp维护移动k次，注意移动数组时倒序进行填充，防止覆盖，时间复杂度O(kn)，但是超时。
- 数组翻转：比较巧妙，先整体翻转，在将0 ~ k - 1和k - 1 ~ n - 1进行翻转。
代码实现：
class Solution { // 使用辅助数组 public void rotate(int[] nums, int k) { int n = nums.length; int[] tmp = new int[n]; for (int i = 0; i < n; i++) { tmp[(i + k) % n] = nums[i]; } System.arraycopy(tmp, 0, nums, 0, n); } // 模拟移动（超时！） public void rotate(int[] nums, int k) { int n = nums.length; k %= n; for (int i = 0; i < k; i++) { int temp = nums[n - 1]; for (int j = n - 1; j > 0; j--) { nums[j] = nums[j - 1]; } nums[0] = temp; } } // 数组翻转（先整体翻转，再翻转部分） public void rotate(int[] nums, int k) { int n = nums.length; k %= n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } private void reverse(int[] nums, int i, int j) { while (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i++; j--; } } }
2.寻找旋转排序数组中的最小值（153 - 中）
题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。请你找出并返回数组中的 最小元素 。
示例 :
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
思路：本题可以直接遍历获取最小值，但是考察点二分查找。注意体会二分查找的思想，不要背模板，这里可以画个折线看看。
注：代码中比较元素取数组最后一个元素，也可以取任意一个元素。
代码实现：
public int findMin(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (nums[mid] > nums[r]) { l = mid + 1; } else { r = mid; } } return nums[l]; }
3.寻找旋转排序数组中的最小值II（154 - 难）
题目描述：整数数组 nums 按升序排列，数组中的值 可能存在重复值 。返回数组中的 最小元素 。同 剑指 Offer 11. 旋转数组的最小数字
示例 :
输入：nums = [2,2,2,0,1] 输出：0
思路：本题可以直接遍历获取最小值，但是考察点二分查找，与上题不同的是数组中可能含有重复值，但是二分的本质是二段性，并非单调性，所以我们还以使用二分。但时间复杂度可能退化O(n)，即全部是一种元素。
注意：由于重复元素的存在，我们并不能确定 nums[mid]究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 nums[r] 是不是最小值，都有一个它的「替代品」nums[mid]，因此我们可以忽略二分查找区间的右端点。
代码实现：
public int findMin(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (nums[mid] > nums[r]) { l = mid + 1; } else if (nums[mid] < nums[r]){ r = mid; } else { r--; } } return nums[l]; }
4.搜索旋转排序数组（33 - 中）
题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 :
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
思路：本题考查二分查找，但是二分查找要求数组有序，关键：
- 先通过mid和nums[r]（任意元素）比较确定有序区间在mid左边还是右边, 如T153
- 再确定目标元素target在哪边!，这时我们就可以直接根据target位置进行二分查找了。
代码实现：
class Solution { // 直接搜索 public int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; } } return -1; } // 二分查找 public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] == target) return mid; if (nums[mid] > nums[r]) { if (target >= nums[l] && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (target > nums[mid] && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } } return -1; } }
5.搜索旋转排序数组II（81 - 中）
题目描述：整数数组 nums 按升序排列（单调不减），数组中的值 可能存在重复值 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 :
输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true
思路：经过上述各题的过度，直接使用二分解法。与33题基本相同。不同的是含有重复元素。
时间复杂度：对于这种含重复元素的二分查找问题，最坏时间复杂度O(n)，即整个数组都是同一个数，最好时间复杂度O(nlogn)。
代码实现：
public boolean search(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] == target) return true; if (nums[mid] > nums[r]) { if (target >= nums[l] && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else if (nums[mid] < nums[r]) { if (target > nums[mid] && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } else { r--; } } return false; }
6.在排序数组中查找目标值的首尾元素的索引（34 - 中）
题目描述：给定一个按照升序排列的整数数组 nums，可能含有重复值，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
要求：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 :
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
思路：代码1在极端情况下，时间复杂度退化为O(n)，不符合要求，但容易理解，实现简单。
其实，我们只需要找两个索引即可，大于target - 1的索引（即目标值的起始索引）和第一个大于target的数的索引 - 1，时间复杂度O(nlogn)，只调用了两次二分查找。
代码实现：
// 代码1 public int[] searchRange(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] == target) { int start = mid, end = mid; while (start >= 0 && nums[start] == target) start--; while (end < n && nums[end] == target) end++; return new int[] {start + 1, end - 1}; } else if (nums[mid] > target) { r = mid - 1; } else { l = mid + 1; } } return new int[] {-1, -1}; } // 代码2 public int[] searchRange(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; int leftIdx = binarySearch(nums, target - 1); int rightIdex = binarySearch(nums, target) - 1; if (leftIdx <= rightIdex && nums[leftIdx] == target && nums[rightIdex] == target) { return new int[] {leftIdx, rightIdex}; } return new int[] {-1, -1}; } // 返回大于target的第一个索引值 public int binarySearch(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1, ans = nums.length; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] > target) { r = mid - 1; ans = mid; } else { l = mid + 1; } } return ans; }
7.面试题：10.03（补充）
题目描述：返回目标元素的第一个索引，即索引值最小的那个（如果存在），不存在返回-1。
示例 :
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5 输出: 8（元素5在该数组中的索引）
思路：本题是T82和T34的思路的融合，但注意由于数组是经过旋转，所以不能像T34查找边界。类似这种情况旋转数组：[5,5,5,1,2,3,4,5] 目标值：5，返回的是7，却不是0。
- 如果左边索引满足条件，直接返回
- 二分，mid符合，但是我们找最小的，所以要更新右边界。
- mid不符合，找升序区间继续二分
代码实现：
public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while (l <= r) { if (nums[l] == target) return l; int mid = l + ((r - l) >> 1); // 索引mid的值是目标值（左边可能还有更小的索引值），更新右边界 if (nums[mid] == target) r = mid; if (nums[mid] > nums[l]) { if (target >= nums[l] && target <= nums[mid]) { r = mid; } else { l = mid + 1; } } else if (nums[mid] < nums[l]) { if (target >= nums[mid] && target <= nums[r]) { l = mid; } else { r = mid - 1; } } else { l++; } } return -1; }
8.山脉数组的峰顶索引（852 - 易）
题目描述：符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 :
输入：arr = [0,2,1,0] 输出：1
思路：本题考察点二分查找，只不过二分的判断条件有点不同。即通过mid相邻点判断最大值所在区间。
代码实现：
public int peakIndexInMountainArray(int[] arr) { int n = arr.length; int l = 0, r = n - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (arr[mid] < arr[mid + 1]) { l = mid + 1; } else { r = mid; } } return l; }
9.山脉数组中查找目标值（1095 - 难）
题目描述：给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
示例 :
输入：array = [1,2,3,4,5,3,1], target = 3 输出：2 解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
思路：上一题的升级，我们寻找包含重复元素的最小索引值。类比面试题10.03。两阶段：
- 找到最大值索引，T852
- 分别在升序和降序区间找目标值。
时间复杂度O(nlogn)，进行三次二分查找（也可能两次）。
代码实现：
public int findInMountainArray(int target, MountainArray mountainArr) { // 1.查找峰顶索引 int n = mountainArr.length(); int l = 0, r = n - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (mountainArr.get(mid) < mountainArr.get(mid + 1)) { l = mid + 1; } else { r = mid; } } // 2.对升序和降序数组分别进行二分查找(用flag标识升序和降序区间) int idx = binarySearch(target, mountainArr, 0, l, true); return idx != -1 ? idx : binarySearch(target, mountainArr, l + 1, n - 1, false); } public int binarySearch(int target, MountainArray mountainArr, int l, int r, boolean flag) { while (l <= r) { int mid = l + ((r - l) >> 1); if (mountainArr.get(mid) == target) return mid; if (mountainArr.get(mid) < target) { l = flag ? mid + 1 : l; r = flag ? r : mid - 1; } else { r = flag ? mid - 1 : r; l = flag ? l : mid + 1; } } return -1; }
10.两数相除（29 - 中）
思路：由于题目限定了我们不能使用乘法、除法和 mod 运算符。
核心：我们可以先实现一个「倍增乘法」，然后利用对于 x 除以 y，结果 x / y 必然落在范围 [0, x] 的规律进行二分。
注意：long mid = l + r + 1 >> 1，之前的用法会超时？
public int divide(int a, int b) { long x = a, y = b; boolean isNeg = (x < 0 && y > 0) || (x > 0 && y < 0); if (x < 0) x = -x; if (y < 0) y = -y; long l = 0, r = x; while (l < r) { long mid = l + r + 1 >> 1; if (mul(mid, y) <= x) { l = mid; } else { r = mid - 1; } } long ans = isNeg ? -l : l; if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE; return (int)ans; } // 倍乘函数 public long mul(long a, long k) { long ans = 0; while (k > 0) { if ((k & 1) == 1) ans += a; k >>= 1; a += a; } return ans; }
