315. Count of Smaller Numbers After Self

cnio 發布于2019-08-14 17:34 / 2083人閱讀

摘要：題目鏈接的題，用來做，這種求有多少的題一般都是。里多加一個信息表示以為的節點數。也可以做，因為是統計有多少的，其實就是求從最小值到的。的是，要做一個映射，把的值映射到之間。所以先把給一下，用一個來做映射。還有的方法，參考

315. Count of Smaller Numbers After Self

題目鏈接：https://leetcode.com/problems...

divide and conquer的題，用bst來做，這種求有多少smaller的題一般都是bst。node里多加一個信息：size表示以node為subtree的節點數。

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也可以做，因為是統計有多少smaller的，其實就是求從最小值到nums[i] - 1的sum。tree的index是nums[i]，要做一個映射，把nums[i]的值映射到[1, # of unique numbers in nums]之間。所以先把array給sort一下，用一個map來做映射。

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/...

GPU云服務器云服務器 Smaller Numbers 315cdn after()

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66675.html

leetcode315. Count of Smaller Numbers After Self

摘要：當我們希望查詢時，則從根節點開始尋找其所在的區間，如果位于左側區間，則查詢左子樹啊，如果位于右側區間，則查詢右子樹。如果橫跨了分割點，則分別查詢左子樹的部分和右子樹的部分。題目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...

elarity 2019-08-15 15:09 評論0 收藏0
Leetcode[315] Count of Smaller Numbers After Self

摘要：復雜度思路每遍歷到一個數，就把他到已有的中。對于每一個，維護一個和一個自身的數目。比如，然后每次遍歷到一個數，就把對應位置的值加一。比如碰到之后，就變成，然后統計的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...

dack 2019-08-14 16:41 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self

摘要：我們建立的，其中解決重復值的問題，記錄左子樹的節點數。給定要找的點，這里的規律就是，往右下走，說明當前點和當前的的左子樹的值全部比小。我們走到要向右，這是左子樹沒變化，這里也不變。題目細節描述參看leetcode。今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前，請思考這個問題。在BST找到所有比Node P小的節點...

Little_XM 2019-08-14 17:20 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節點，或者只有一個子樹。思想來自于的代碼實現。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0
[LeetCode] 315. Count of Smaller Numbers After Sel

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...

FingerLiu 2019-08-16 13:53 評論0 收藏0