1. 矩阵
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。
示例1：
1
2
3
| 输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。
|
示例2：
1
2
| 输入：grid = [[3,2],[1,0]]
输出：0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int countNegatives(int[][] grid) {
int count = 0;
for(int i = 0 ; i < grid.length; i++) {
count += countRowNegatives(grid[i]);
}
return count;
}
private int countRowNegatives(int[] row) {
int left = 0;
int right = row.length;
while(left < right) {
int mid = left + (right - left) / 2;
if(row[mid] >= 0) {
left = mid + 1;
} else {
right = mid;
}
}
return row.length - 1 - left + 1;
}
}
|
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例1：
1
2
| 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
|
示例2：
1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int left = 0;
int col = matrix[0].length;
int row = matrix.length;
int right = row * col;
while(left < right) {
int mid = left + (right - left) / 2;
if(matrix[mid / col][mid % col] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if(left < row * col && target == matrix[left / col][left % col]) {
return true;
}
return false;
}
}
|
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
示例1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 输入：mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
|
示例2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 输入：mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
输出：[0,2]
解释：
每行中的军人数目：
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
从最弱到最强对这些行排序后得到 [0,2,3,1]
|
提示：
m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i] [j] 不是 0 就是 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
| class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
List<int[]> list = new ArrayList<>();
for(int i = 0; i < mat.length; i++) {
int left = 0;
int right = mat[i].length;
while(left < right) {
int mid = left + (right - left) / 2;
if(mat[i][mid] == 1) {
left = mid + 1;
} else {
right = mid;
}
}
list.add(new int[]{left, i});
}
PriorityQueue<int[]> heap = new PriorityQueue(new Comparator <int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] != o2[0]) {
return o1[0] - o2[0];
} else {
return o1[1] - o2[1];
}
}
});
for(int i = 0; i < list.size(); i++) {
heap.offer(list.get(i));
}
int[] res = new int[k];
for(int i = 0; i < k; i++) {
res[i] = heap.poll()[1];
}
return res;
}
}
|
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
示例1：
1
2
3
| 输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。
|
示例2：
1
2
3
| 输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。
|
示例3：
1
2
3
| 输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。
|
提示：
2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3
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
| class Solution {
public boolean checkIfExist(int[] arr) {
Arrays.sort(arr);
int poAndNaLine = binarySearch(arr, 0, arr.length, 0);
for(int i = poAndNaLine - 1; i >= 0; i--) {
int res = binarySearch(arr, 0, i, arr[i] * 2);
if(res < arr.length && arr[res] == arr[i] * 2) {
return true;
}
}
for(int i = poAndNaLine; i < arr.length; i++) {
int res = binarySearch(arr, i + 1, arr.length, arr[i] * 2);
if(res < arr.length && arr[res] == arr[i] * 2) {
return true;
}
}
return false;
}
private int binarySearch(int[] arr, int left, int right, int target) {
while(left < right) {
int mid = left + (right - left) / 2;
if(arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
|
