資訊專欄INFORMATION COLUMN
摘要：題目鏈接的題，用來(lái)做，這種求有多少的題一般都是。里多加一個(gè)信息表示以為的節(jié)點(diǎn)數(shù)。也可以做，因?yàn)槭墙y(tǒng)計(jì)有多少的，其實(shí)就是求從最小值到的。的是，要做一個(gè)映射，把的值映射到之間。所以先把給一下，用一個(gè)來(lái)做映射。還有的方法，參考
315. Count of Smaller Numbers After Self
題目鏈接：https://leetcode.com/problems...
divide and conquer的題，用bst來(lái)做，這種求有多少smaller的題一般都是bst。node里多加一個(gè)信息：size表示以node為subtree的節(jié)點(diǎn)數(shù)。
public class Solution {
public List countSmaller(int[] nums) {
/* binary search tree
*/
int n = nums.length;
LinkedList res = new LinkedList();
if(n == 0) return res;
res.add(0);
Node root = new Node(nums[n-1]);
for(int i = n - 2; i >= 0; i--) {
res.addFirst(findSmaller(root, nums[i]));
}
return res;
}
private int findSmaller(Node root, int value) {
int res = 0;
while(root != null) {
root.size += 1;
if(root.val < value) {
// add root and all left nodes
res += 1 + (root.left == null ? 0 : root.left.size);
if(root.right == null) {
root.right = new Node(value);
break;
}
root = root.right;
}
else {
if(root.left == null) {
root.left = new Node(value);
break;
}
root = root.left;
}
}
return res;
}
class Node {
int val;
Node left;
Node right;
// count the size of this subtree
int size;
Node(int val) { this.val = val; this.size = 1; }
}
}
binary index tree也可以做，因?yàn)槭墙y(tǒng)計(jì)有多少smaller的，其實(shí)就是求從最小值到nums[i] - 1的sum。tree的index是nums[i]，要做一個(gè)映射，把nums[i]的值映射到[1, # of unique numbers in nums]之間。所以先把a(bǔ)rray給sort一下，用一個(gè)map來(lái)做映射。
public class Solution {
public List countSmaller(int[] nums) {
/* binary index tree
*/
// reflection first, key: nums[i], value: order
Map map = new HashMap();
int[] sorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted);
// record the order
int idx = 1;
for(int i = 0; i < nums.length; i++) {
if(!map.containsKey(sorted[i])) map.put(sorted[i], idx++);
}
// range will be [1, idx]
BIT t = new BIT(idx);
LinkedList res = new LinkedList();
for(int i = nums.length - 1; i >= 0; i--) {
int sum = t.sum(map.get(nums[i]) - 1);
res.addFirst(t.sum(map.get(nums[i]) - 1));
t.add(map.get(nums[i]), 1);
}
return res;
}
class BIT {
int[] tree;
int n;
BIT(int n) { this.n = n; tree = new int[n]; }
// sum the smaller elements
protected int sum(int i) {
int res = 0;
while(i > 0) {
res += tree[i];
i -= (i & -i);
}
return res;
}
protected void add(int i, int val) {
while(i < n) {
tree[i] += val;
i += (i & -i);
}
}
}
}
還有merge sort的方法，參考discussion：
https://discuss.leetcode.com/...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66675.html
摘要：當(dāng)我們希望查詢時(shí)，則從根節(jié)點(diǎn)開(kāi)始尋找其所在的區(qū)間，如果位于左側(cè)區(qū)間，則查詢左子樹(shù)啊，如果位于右側(cè)區(qū)間，則查詢右子樹(shù)。如果橫跨了分割點(diǎn)，則分別查詢左子樹(shù)的部分和右子樹(shù)的部分。 題目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要：復(fù)雜度思路每遍歷到一個(gè)數(shù)，就把他到已有的中。對(duì)于每一個(gè)，維護(hù)一個(gè)和一個(gè)自身的數(shù)目。比如，然后每次遍歷到一個(gè)數(shù)，就把對(duì)應(yīng)位置的值加一。比如碰到之后，就變成，然后統(tǒng)計(jì)的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...
摘要：我們建立的，其中解決重復(fù)值的問(wèn)題，記錄左子樹(shù)的節(jié)點(diǎn)數(shù)。給定要找的點(diǎn)，這里的規(guī)律就是，往右下走，說(shuō)明當(dāng)前點(diǎn)和當(dāng)前的的左子樹(shù)的值全部比小。我們走到要向右，這是左子樹(shù)沒(méi)變化，這里也不變。 題目細(xì)節(jié)描述參看leetcode。 今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個(gè)題目之前，請(qǐng)思考這個(gè)問(wèn)題。在BST找到所有比Node P小的節(jié)點(diǎn)...
摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來(lái)，最后回原來(lái)正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹(shù)。思想來(lái)自于的代碼實(shí)現(xiàn)。 跳過(guò)總結(jié)請(qǐng)點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是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...
閱讀 1896·2021-11-11 16:55
閱讀 2106·2021-10-08 10:13
閱讀 755·2019-08-30 11:01
閱讀 2166·2019-08-29 13:19
閱讀 3293·2019-08-28 18:18
閱讀 2631·2019-08-26 13:26
閱讀 588·2019-08-26 11:40
閱讀 1879·2019-08-23 17:17
