資訊專欄INFORMATION COLUMN
摘要：復(fù)雜度思路每遍歷到一個數(shù)，就把他到已有的中。對于每一個，維護一個和一個自身的數(shù)目。比如，然后每次遍歷到一個數(shù)，就把對應(yīng)位置的值加一。比如碰到之后，就變成，然后統(tǒng)計的和。
Leetcode[315] Count of Smaller Numbers After Self
Binary Search Treeou are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
復(fù)雜度
O(NlgN), O(N)
思路
每遍歷到一個數(shù)，就把他insert到已有的BST中。對于每一個node，維護一個leftsum和一個自身的cnt數(shù)目。所以對于一個Node來說，比他小的值，應(yīng)該是每次向右走的時候，就將結(jié)果累積到prenum中，其中prenum = node.leftsum + node.cnt
代碼
class Node {
int val;
int leftSum;
int cnt;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
LinkedList res;
public List countSmaller(int[] nums) {
res = new LinkedList<>();
Node root = new Node();
for(int i = nums.length - 1; i >= 0; i --) {
helper(nums[i], root, 0);
}
}
public Node helper(int val, Node root, int preNum) {
if(root == null) {
res.addFirst(preNum);
return new Node(val);
}
if(root.val == val) {
root.cnt ++;
res.addFirst(preNum + root.leftSum);
}
else if(root.val > val) {
root.leftSum ++;
root.left = helper(val, root.left, preNum);
}
else {
root.right = helper(val, root.right, preNum + root.leftSum + root.cnt);
}
return root;
}
Binary Index Tree
復(fù)雜度
O(NlgN), O(N)
思路
建立一個包含從min到max的數(shù)組，[5,2,6,1]，然后對于每一個數(shù)，考慮從Min到比這個數(shù)的小的所有數(shù)的和。
比如[1,2,3,4,5,6]=[0,0,0,0,0,0]，然后每次遍歷到一個數(shù)，就把對應(yīng)位置的值加一。
比如碰到1之后，就變成[1,0,0,0,0,0]，然后統(tǒng)計sum[val - 1]的和。
代碼
int[] BItree; public ListcountSmaller(int[] nums) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; LinkedList res = new LinkedList<>(); if(nums == null || nums.length == 0) return res; // for(int val : nums) { min = Math.min(min, val); } int diff = 1 - min; for(int i = 0; i < nums.length; i ++) { nums[i] += diff; max = Math.max(max, nums[i]); } // BItree = new int[max + 1]; for(int i = nums.length - 1; i >= 0; i --) { res.addFirst(getSum(nums[i] - 1)); update(nums[i], BItree.length); } return res; } public int getSum(int index) { int res = 0; while(index > 0) { res += BItree[index]; index -= index & (-index); } return res; } public void update(int index, int len) { while(index < len) { BItree[index] ++; index += index & (-index); } }
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66253.html
摘要：當(dāng)我們希望查詢時，則從根節(jié)點開始尋找其所在的區(qū)間，如果位于左側(cè)區(qū)間，則查詢左子樹啊，如果位于右側(cè)區(qū)間，則查詢右子樹。如果橫跨了分割點，則分別查詢左子樹的部分和右子樹的部分。 題目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要：我們建立的，其中解決重復(fù)值的問題，記錄左子樹的節(jié)點數(shù)。給定要找的點，這里的規(guī)律就是，往右下走，說明當(dāng)前點和當(dāng)前的的左子樹的值全部比小。我們走到要向右，這是左子樹沒變化，這里也不變。 題目細節(jié)描述參看leetcode。 今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前，請思考這個問題。在BST找到所有比Node P小的節(jié)點...
摘要：題目鏈接的題，用來做，這種求有多少的題一般都是。里多加一個信息表示以為的節(jié)點數(shù)。也可以做，因為是統(tǒng)計有多少的，其實就是求從最小值到的。的是，要做一個映射，把的值映射到之間。所以先把給一下，用一個來做映射。還有的方法，參考 315. Count of Smaller Numbers After Self 題目鏈接：https://leetcode.com/problems... divi...
摘要：題目意思就是要一個個的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結(jié)果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節(jié)點，或者只有一個子樹。思想來自于的代碼實現(xiàn)。 跳過總結(jié)請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...
Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...
閱讀 2406·2021-10-09 09:44
閱讀 2140·2021-10-08 10:05
閱讀 3432·2021-07-26 23:38
閱讀 3008·2019-08-28 18:16
閱讀 820·2019-08-26 11:55
閱讀 1827·2019-08-23 18:29
閱讀 2042·2019-08-23 18:05
閱讀 1373·2019-08-23 17:02
