剑指 Offer 04. 二维数组中的查找 & 剑指 Offer 05. 替换空格
题目一:二维数组中的查找
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
给定 target = 5
,返回 true
。
给定 target = 20
,返回 false
。
限制:
0 <= n <= 1000
0 <= m <= 1000
解题方法一
/**
* 暴力循环
* 执行用时:
* 0 ms, 在所有 Java 提交中击败了100.00%的用户
* 内存消耗:
* 47.1 MB, 在所有 Java 提交中击败了5.04%的用户
*
* @param matrix
* @param target
* @return
*/
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null){
return false;
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i].length == 0){
continue;
}
if (matrix[i][0] > target){
break;
}else {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == target){
return true;
}
}
}
}
return false;
}
解题方法二
/**
* 具体操作为从矩阵左下角元素开始遍历,并与目标值对比:
* 当 matrix[i][j] > target 时: 行索引向上移动一格(即 i--),即消去矩阵第 i 行元素;
* 当 matrix[i][j] < target 时: 列索引向右移动一格(即 j++),即消去矩阵第 j 列元素;
* 当 matrix[i][j] == target 时: 返回 true。
* 如果越界,则返回 false。
*
* 时间复杂度为 O(M+N),其中,N 和 M 分别为矩阵行数和列数,此算法最多循环 M + N 次。
* 空间复杂度为 O(1)。
* @param matrix
* @param target
* @return
*/
public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
//初始化 i 和 j 为数组左下角元素
int i = matrix.length - 1;
int j = 0;
//如果 i 和 j 没有越界继续判断
while(i >= 0 && j < matrix[0].length){
if(matrix[i][j] > target){
//行索引向上移动一格(即 i-- ),即消去矩阵第 i 行元素
i--;
}else if(matrix[i][j] < target){
//列索引向右移动一格(即 j++ ),即消去矩阵第 j 列元素
j++;
}else{
//找到目标值,直接返回 ture
return true;
}
}
//没有找到目标值,返回 false
return false;
}
解题方法三
/**
* 逐行二分
* 时间复杂度:O(mlogn)
* 空间复杂度:O(1)
* @param matrix
* @param target
* @return
*/
public static boolean findNumberIn2DArray3(int[][] matrix, int target) {
if(matrix==null || matrix.length==0||matrix[0].length==0)
return false;
int m = matrix.length;
int n = matrix[0].length;
for(int i = 0; i < m; i++){
if(target<matrix[i][0] || target > matrix[i][n-1])
continue;
int left = 0;
int right = n-1;
while(left <= right){
int mid = (right-left)>>1+left;
if(matrix[i][mid]==target)
return true;
if(matrix[i][mid]<target){
left = mid+1;
}else{
right = mid-1;
}
}
}
return false;
}
题目二:替换空格
请实现一个函数,把字符串 s
中的每个空格替换成"%20"。
示例 1:
输入:s = "We are happy." 输出:"We%20are%20happy."
限制:
0 <= s 的长度 <= 10000
解题方法
public static String replaceSpace(String s) {
return s.replace(" ", "%20");
}
/**
* 字符数组
* 由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。
* 建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符。
*
* 时间复杂度:O(n)。遍历字符串 s 一遍。
* 空间复杂度:O(n)。额外创建字符数组,长度为 s 的长度的 3 倍。
* @param s
* @return
*/
public static String replaceSpace2(String s) {
int strLen = s.length();
char[] str = new char[strLen * 3];
int size = 0;
for (int i = 0; i < strLen; i++) {
char c = s.charAt(i);
if (c == ' '){
str[size++] = '%';
str[size++] = '2';
str[size++] = '0';
}else {
str[size++] = c;
}
}
return new String(str, 0, size);
}
微信关注
阅读剩余
版权声明:
作者:理想
链接:https://www.imyjs.cn/archives/572
文章版权归作者所有,未经允许请勿转载。
THE END