311. Sparse Matrix Multiplication
稀疏矩阵的计算。稀疏矩阵的特点是有大量的0,如果采用暴力算法则比然会有很多无意义的计算。
C[ i ][ j ] += A[ i ] [ k ] * B[ k ] [ j ]
我们首先遍历A数组,要确保A[i][k]不为0,才继续计算,然后我们遍历B矩阵的第k行,如果B[K][J]不为0,我们累加结果矩阵res[i][j] += A[i][k] * B[k][j]
class Solution { public int[][] multiply(int[][] A, int[][] B) { int m = A.length, n = A[0].length, nB = B[0].length; int[][] C = new int[m][nB]; for(int i = 0; i < m; i++){ for(int k = 0; k < n; k++){ if(A[i][k] != 0){ for(int j = 0; j < nB; j++){ if(B[k][j] != 0) C[i][j] += A[i][k] * B[k][j]; } } } } return C; } }
378. Kth Smallest Element in a Sorted Matrix
class Solution { public int kthSmallest(int[][] matrix, int k) { int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1; while(lo < hi){ int count = 0, j = matrix[0].length - 1; int mid = lo + (hi - lo) / 2; for(int i = 0; i < matrix.length; i++){ while(j >= 0 && matrix[i][j] > mid) j--; count += (j + 1); } if(count < k) lo = mid + 1; else hi = mid; } return lo; } }