leetcode热题100-Java解-2025.4.7
69/100
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例略
写完前面的这题纯水题
从右上或左下入手就是个二叉搜索树
解一 dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
return dfs(matrix, target, m - 1, 0);
}
private boolean dfs(int[][] matrix, int target, int i, int j) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
return false;
}
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
return dfs(matrix, target, i - 1, j);
}else {
return dfs(matrix, target, i, j + 1);
}
}
|
解二 二分查找
针对这题可以使用
题目保证了本行的每个元素都大于上一行的任一元素
先排查行，再二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i = m - 1;
int j = 0;
while( target < matrix[i][j] ){
i--;
if( i < 0 ){
return false;
}
}
int k = n - 1;
while( j <= k ){
int mid = (j + k) / 2;
if( matrix[i][mid] == target ){
return true;
}else if( matrix[i][mid] < target ){
j = mid + 1;
}else{
k = mid - 1;
}
}
return false;
}
|
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
1
2
| 输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
|
示例 2：
1
2
| 输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
|
示例 3：
1
2
| 输入：nums = [], target = 0
输出：[-1,-1]
|
解一 递归
我是递归高手
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int index = 0;
if (nums.length == 1) {
return nums[0] == target ? 0 : -1;
}
index = findIndex(nums, left, right);
int res1 = binarySearch(nums, target, 0, index - 1);
int res2 = binarySearch(nums, target, index, nums.length - 1);
return res1 == res2 || res1 != -1 ? res1 : res2;
}
private int findIndex(int[] nums, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
if(right - left == 1) {
return right;
}
return findIndex(nums, mid, right);
}else if( nums[mid] < nums[right]) {
int begin = nums[mid];
for (int i = mid; i >= 1; i--) {
if (nums[i] < nums[i - 1]) {
return i;
}
}
return -1;
}else {
return -1;
}
}
private int binarySearch(int[] nums, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}else if (nums[mid] > target) {
if (mid >= 1) {
return binarySearch(nums, target, left, mid - 1);
}
}else {
if (mid <= nums.length - 1) {
return binarySearch(nums, target, mid + 1, right);
}
}
return -1;
}
|
解二 官方解
相对来看，我的解法等于把数组遍历了两遍，第一遍区分有序部分，第二遍二分查找
O(2n) ~ O(n)
大致是这个效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
|
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转
7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
1
2
3
| 输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
|
示例 2：
1
2
3
| 输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
|
示例 3：
1
2
3
| 输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
|
解一 递归，复用上一题写的findIndex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public int findMin(int[] nums) {
int index = findIndex(nums, 0, nums.length - 1);
if (index == -1) {
return nums[0];
}
return nums[index];
}
private int findIndex(int[] nums, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
if(right - left == 1) {
return right;
}
return findIndex(nums, mid, right);
}else if( nums[mid] < nums[right]) {
int begin = nums[mid];
for (int i = mid; i >= 1; i--) {
if (nums[i] < nums[i - 1]) {
return i;
}
}
return -1;
}else {
return -1;
}
}
|
解二 官方解，迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int findMin(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) {
high = pivot;
} else {
low = pivot + 1;
}
}
return nums[low];
}
|
