2022年4月10日
算法基础第一天
这题回顾一下二分法，要找最左和最右的边界，在mid = target之后，继续移动mid的位置即可。
/**
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9
* @author zeroheart
*
*/
public class Question34 {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1,-1};
res[0] = binarySearch(nums, target, 1);
res[1] = binarySearch(nums, target, 0);
return res;
}
public int binarySearch(int[] nums, int target, int left){
int res = -1;
int low = 0; int high = nums.length - 1;
int mid = 0;
while (low <= high){
mid = low + (high-low) / 2;
if(nums[mid]<target){
low = mid + 1;
}else if(nums[mid]>target){
high = mid - 1;
}else {
// 虽然已经找到了，不过不一定是最左边的或者最右边的
res = mid;
if(left == 1){
// 如果要找的是最左的，右边的指针继续减小。
high = mid - 1;
}else {
low = mid + 1;
}
}
}
return res;
}
public int[] searchRange1(int[] nums, int target) {
// 通过了，但是没用到算法
int[] res = new int[]{-1,-1};
for(int i = 0; i<nums.length; i++){
if(nums[i] == target && res[0] == -1){
res[0] = i;
}
if(nums[i] == target && res[0] != -1 && i == nums.length - 1){
res[1] = i;
break;
}
if(nums[i] > target && res[0] != -1){
res[1] = i-1;
break;
}
}
if(res[0] == -1){
res[1] = -1;
}
if(res[1] < res[0]){
res[1] = res[0];
}
return res;
}
}
旋转排序数组，nums[0]是一个分界点。这题也是利用二分法，确定是在高的一侧还是低的一层之后，在比较target的大小来移动指针。
/**
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
* @author zeroheart
*
*/
public class Question33 {
public int search(int[] nums, int target) {
int res = -1;
int low = 0;
int high = nums.length - 1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
}
// nums[0] 是一个分界点
if (nums[0] <= nums[mid]) {
// mid 出现在高的一侧
// 看target的情况，移动指针
if (nums[0] <= target && target < nums[mid]) {
// 注意这里的<=
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[nums.length - 1]) {
// 注意这里的<=
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return res;
}
}
这也是二分法的变种，二位数组的坐标要转一下。注意二分的high = len -1；
/**
74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
* @author zeroheart
*
*/
public class Question74 {
public boolean searchMatrix(int[][] matrix, int target) {
// 实际就是二分法，就是要做一次坐标转化
int m = matrix.length;
int n = matrix[0].length;
int low = 0; int high = m * n - 1;
while (low <= high){
int mid = low + (high - low) / 2;
int tmp = matrix[mid/n][mid%n];
if(tmp == target) return true;
if(tmp < target) {
low = mid + 1;
}else {
high = mid - 1;
}
}
return false;
}
}