240. 搜索二維矩陣 II

問題描述

編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。

解題思路1-二分查找行

遍歷每一行的首元素，如果首元素小于target，代表target有可能存在該行；再針對每一行進行二分查找。

代碼實現(xiàn)1-二分查找行

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行數(shù)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-雙指針遍歷

利用數(shù)組中右下角的元素一定最大的思想
每次都可以按行/列對搜索空間進行縮減

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //求行數(shù)n，列數(shù)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. 從前序與中序遍歷序列構造二叉樹

問題描述

根據(jù)一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意:你可以假設樹中沒有重復的元素。

解題思路

dfs遞歸構建。

• 可以利用hashMap減少每次定位根節(jié)點在中序數(shù)組中的位置所花費的時間

代碼實現(xiàn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //key為數(shù)組中元素的值，value為對應的索引
    private HashMap<Integer, Integer> mapInorder = new HashMap<>();
    //將數(shù)組轉為全局變量，節(jié)省空間
    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表示前序遍歷數(shù)組在preorder中的開始位置、結束位置
   // inStart, int inEnd表示中序遍歷數(shù)組在inorder中的開始位置、結束位置
    public TreeNode getTree(int preStart, int preEnd, int inStart, int inEnd){
        //根節(jié)點為前序遍歷數(shù)組的首元素
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);

        if(preStart == preEnd){
            //若樹只有一個節(jié)點，則直接返回
            return root;
        }

        //root節(jié)點在中序數(shù)組中的索引
        int rootIn = mapInorder.get(rootVal);
       
        //【構建左子樹】
        //左子樹節(jié)點的數(shù)量
        int leftNodes = rootIn - inStart;
        if(leftNodes > 0){
            root.left = getTree(preStart + 1, preStart + leftNodes, inStart, rootIn - 1);
        }
        
        //【構建右子樹】
        //右子樹節(jié)點的數(shù)量
        int rightNodes = inEnd - rootIn;
        if(rightNodes > 0){
            root.right = getTree(preStart + leftNodes + 1, preStart + leftNodes + rightNodes , rootIn + 1,  inEnd);
        }

        return root;
    }
}