Leetcode[315] Count of Smaller Numbers After Self

dack 發布于2019-08-14 16:41 / 2594人閱讀

摘要：復雜度思路每遍歷到一個數，就把他到已有的中。對于每一個，維護一個和一個自身的數目。比如，然后每次遍歷到一個數，就把對應位置的值加一。比如碰到之后，就變成，然后統計的和。

Leetcode[315] Count of Smaller Numbers After Self

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

Binary Search Tree

復雜度
O(NlgN), O(N)

思路
每遍歷到一個數，就把他insert到已有的BST中。對于每一個node，維護一個leftsum和一個自身的cnt數目。所以對于一個Node來說，比他小的值，應該是每次向右走的時候，就將結果累積到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

復雜度
O(NlgN), O(N)

思路
建立一個包含從min到max的數組，[5,2,6,1]，然后對于每一個數，考慮從Min到比這個數的小的所有數的和。
比如[1,2,3,4,5,6]=[0,0,0,0,0,0]，然后每次遍歷到一個數，就把對應位置的值加一。
比如碰到1之后，就變成[1,0,0,0,0,0]，然后統計sum[val - 1]的和。

代碼

int[] BItree;

public List countSmaller(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);
    }
}

云服務器 GPU云服務器 Smaller Numbers 315cdn LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66253.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。今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前，請思考這個問題。在BST找到所有比Node P小的節點...

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

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

cnio 2019-08-14 17:34 評論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