240. 搜索二維矩陣 II
問題描述
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 target 。該矩陣具有以下特性:
每行的元素從左到右升序排列。
每列的元素從上到下升序排列啥么。
解題思路1-二分查找行
遍歷每一行的首元素,如果首元素小于target菲驴,代表target有可能存在該行;再針對每一行進(jìn)行二分查找骑冗。
代碼實現(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;
}
}
- 時間復(fù)雜度為O(nlogn)
解題思路2-雙指針遍歷
利用數(shù)組中右下角的元素一定最大的思想
每次都可以按行/列對搜索空間進(jìn)行縮減
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;
}
}
- 時間復(fù)雜度O(m + n)
105. 從前序與中序遍歷序列構(gòu)造二叉樹
問題描述
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹巧涧。
注意:你可以假設(shè)樹中沒有重復(fù)的元素。
解題思路
dfs遞歸構(gòu)建遥倦。
- 可以利用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為對應(yīng)的索引
private HashMap<Integer, Integer> mapInorder = new HashMap<>();
//將數(shù)組轉(zhuǎn)為全局變量,節(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中的開始位置袒哥、結(jié)束位置
// inStart, int inEnd表示中序遍歷數(shù)組在inorder中的開始位置缩筛、結(jié)束位置
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);
//【構(gòu)建左子樹】
//左子樹節(jié)點的數(shù)量
int leftNodes = rootIn - inStart;
if(leftNodes > 0){
root.left = getTree(preStart + 1, preStart + leftNodes, inStart, rootIn - 1);
}
//【構(gòu)建右子樹】
//右子樹節(jié)點的數(shù)量
int rightNodes = inEnd - rootIn;
if(rightNodes > 0){
root.right = getTree(preStart + leftNodes + 1, preStart + leftNodes + rightNodes , rootIn + 1, inEnd);
}
return root;
}
}