240. 搜索二维矩阵 II

问题描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

解题思路1-二分查找行

遍历每一行的首元素，如果首元素小于target，代表target有可能存在该行；再针对每一行进行二分查找。

代码实现1-二分查找行

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行数n
        int n = matrix.length;

        for(int i = 0; i < n; i++){
            if(matrix[i].length != 0 && matrix[i][0] > target){
                continue;
            }
            if(binarySearch(matrix[i],target) != -1){
                return true;
            }
        }
        return false;
       
    }

    //二分查找法，返回target在行中索引，若不存在返回-1
    public int binarySearch(int[] row, int target){
        int left = 0, right = row.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(row[mid] < target){
                left = mid + 1;
            }else if(row[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
        
    }
}

• 时间复杂度为O(nlogn)

解题思路2-双指针遍历

利用数组中右下角的元素一定最大的思想
每次都可以按行/列对搜索空间进行缩减

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行数n，列数m
        int n = matrix.length, m = matrix[0].length;
        
        int row = n - 1, col = 0;
        while(row >= 0 && col < m){
            if(matrix[row][col] > target){
                row--;
            }else if (matrix[row][col] < target){
                col++;
            }else{
                return true;
            }
        }
        return false; 
    }
}

• 时间复杂度O(m + n)

105. 从前序与中序遍历序列构造二叉树

问题描述

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。

解题思路

dfs递归构建。

• 可以利用hashMap减少每次定位根节点在中序数组中的位置所花费的时间

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //key为数组中元素的值，value为对应的索引
    private HashMap<Integer, Integer> mapInorder = new HashMap<>();
    //将数组转为全局变量，节省空间
    int[] pre;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if(len == 0 || len != inorder.length){
            return null;
        }
        pre = preorder;
        for(int i = 0 ; i < len; i++){
            mapInorder.put(inorder[i], i);
        }
        return getTree(0, len - 1,  0, len - 1);
    }

    // preStart,preEnd表示前序遍历数组在preorder中的开始位置、结束位置
   // inStart, int inEnd表示中序遍历数组在inorder中的开始位置、结束位置
    public TreeNode getTree(int preStart, int preEnd, int inStart, int inEnd){
        //根节点为前序遍历数组的首元素
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);

        if(preStart == preEnd){
            //若树只有一个节点，则直接返回
            return root;
        }

        //root节点在中序数组中的索引
        int rootIn = mapInorder.get(rootVal);
       
        //【构建左子树】
        //左子树节点的数量
        int leftNodes = rootIn - inStart;
        if(leftNodes > 0){
            root.left = getTree(preStart + 1, preStart + leftNodes, inStart, rootIn - 1);
        }
        
        //【构建右子树】
        //右子树节点的数量
        int rightNodes = inEnd - rootIn;
        if(rightNodes > 0){
            root.right = getTree(preStart + leftNodes + 1, preStart + leftNodes + rightNodes , rootIn + 1,  inEnd);
        }

        return root;
    }
}