HOT100–Day22–74. 搜索二维矩阵，34. 在排序数组中查找元素的第一个和最后一个位置，33. 搜索旋转排序数组
每日刷题系列。今天的题目是《力扣HOT100》题单。
题目类型：二分查找。
关键：
今天的题目都是“多次二分”
74题，掌握如何把有序矩阵，flatten成一维。
34题，懂得如何找元素的最左索引。
35题，懂得“翻转有序数组”的特性。如何找最小值的位置？要搜索怎么搜？
74. 搜索二维矩阵
思路：
先竖着二分，找到所在行，再横着二分，找到所在列。
class Solution {
// 先竖着二分，再横着二分
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
int top = 0;
int bottom = n - 1;
int row = 0;
while (top <= bottom) {
row = top + ((bottom - top) >> 1);
if (matrix[row][0] == target) {
return true;
} else if (matrix[row][0] > target) {
bottom = row - 1;
} else if (matrix[row][0] < target) {
if (row == n - 1 || matrix[row + 1][0] > target) {
break;
}
top = row + 1;
}
}
int left = 0;
int right = m - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (matrix[row][mid] == target) {
return true;
} else if (matrix[row][mid] > target) {
right = mid - 1;
} else if (matrix[row][mid] < target) {
left = mid + 1;
}
}
return false;
}
}
思路：
flatten成一维。
关键：计算当前mid在矩阵中的什么位置int x = matrix[mid / m][mid % m];
class Solution {
// 思路：flatten成一维的
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
int left = 0;
int right = n * m - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
// 关键：计算当前mid在矩阵中的什么位置
int x = matrix[mid / m][mid % m];
if (x == target) {
return true;
}
if (x < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
思路：
排除法。
从右上角开始比较。
如果右上角元素小于target，那么这一行直接丢弃，i++，下一行。
如果右上角元素大于target，那么到了所在行了，j–，往左走到尽头。
class Solution {
// 排除法
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
// 从右上角开始
int i = 0;
int j = m - 1;
// 直到左下角
while (i < n && j >= 0) {
if (matrix[i][j] == target) {
return true;
}
// 这里是右上角元素，证明这一行剩余元素全部小于 target，排除
if (matrix[i][j] < target) {
i++;
} else {
// 到所在行了，往左走。
j--;
}
}
return false;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
思路：
多次二分：
先找到任意一个target的索引，从当前位置，往左往右不断二分找target，直到找到最左和最右值。
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int[] res = { -1, -1 };
int mid = findIndex(nums, 0, n - 1, target);
if (mid == -1) {
return res;
} else {
res[0] = mid;
res[1] = mid;
}
int left = mid;
int right = mid;
while (left != -1 || right != -1) {
left = findIndex(nums, 0, left - 1, target);
res[0] = left != -1 ? left : res[0];
right = findIndex(nums, right + 1, n - 1, target);
res[1] = right != -1 ? right : res[1];
}
return res;
}
private int findIndex(int[] nums, int begin, int end, int target) {
int left = begin;
int right = end;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
}
思路：
两次二分。
一次寻找最左的值为target的值
第二次寻找最左的，值为target+1的值。找不到不要紧，是那个位置就行了。减一就是target的最右边。
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = findLeftest(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[] { -1, -1 };
}
int end = findLeftest(nums, target + 1) - 1;
return new int[] { start, end };
}
private int findLeftest(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
33. 搜索旋转排序数组
思路：
两次二分。
第一次，先找到最小值的点，把它划分成两段，这两段都是单调的，可以用二分了。
从这两段里面分别二分，寻找target。
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int i = findMin(nums);
if (target > nums[n - 1]) { // target 在第一段
return lowerBound(nums, -1, i, target); // 开区间 (-1, i)
}
// target 在第二段
return lowerBound(nums, i - 1, n, target); // 开区间 (i-1, n)
}
// 153. 寻找旋转排序数组中的最小值（返回的是下标）
private int findMin(int[] nums) {
int n = nums.length;
int left = -1;
int right = n - 1; // 开区间 (-1, n-1)
while (left + 1 < right) { // 开区间不为空
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[n - 1]) {
right = mid;
} else {
left = mid;
}
}
return right;
}
// 有序数组中找 target 的下标
private int lowerBound(int[] nums, int left, int right, int target) {
while (left + 1 < right) { // 开区间不为空
// 循环不变量：
// nums[right] >= target
// nums[left] < target
int mid = left + ((right - left) >> 1);
if (nums[mid] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
return nums[right] == target ? right : -1;
}
}