剑指 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 = "We are happy."
输出："We%20are%20happy."

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);
    }

微信关注

WeChat