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