lurenaa的博客

😝二叉查找树实现

  有几个难点

  • 递归插入的时候要通过一个辅助变量来更新每个节点的值（low_count）
  • 处理值相同时的情况
    因为插入是沿着一条路径下去的，所以是没有办法在插入的时候更新全部节点的。

    😳方案一是：选择单独在插入之后再来更新节点。

    😳方案二是：更新一边的节点，在这个题目中，我们的选择就是只更新左边的节点，这时Node->low_count代表的就不是全体中比它小的节点数量，而是当前根节点下比它小的数量，而向右移动就是切换根节点。

    因为我们是以根节点标准开始进行比较，所以我们用辅助变量更新节点是更新不到起点以外的地方的。

🥦方案二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    struct Node {
        int low_count;  //统计比它小的节点
        int val;
        shared_ptr<Node> left, right;
        Node(int val, int count) : 
        low_count(count), val(val), left(nullptr), right(nullptr) {}
        int compareTo(int k) {
            if(val < k) 
                return -1;
            else if (val > k) 
                return 1;
            return 0;
        }
    };
    int low_c = 0;
    shared_ptr<Node> insert(shared_ptr<Node> h, int val) {
        if(!h) 
            return make_shared<Node>(val ,0);
        int cmp = h->compareTo(val);
        if(cmp >= 0) {
            h->low_count += 1;
            h->left = insert(h->left, val);
        } 
        else if(cmp < 0) {
            low_c += h->low_count + 1;
            h->right = insert(h->right, val);
        } 
        return h;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> counts(nums.size());
        if(!nums.size())
            return counts;
        counts[0] = 0;
        if(nums.size() == 1) {
            return counts;
        }
        shared_ptr<Node> head = make_shared<Node>(nums.back(), 0);
        for(int i = nums.size() - 2; i >=0 ; -- i){
            low_c = 0;
            head = insert(head, nums[i]);
            counts[i] = low_c;
        }
        return counts;
    }
};

Accepted

16/16 cases passed (64 ms)

Your runtime beats 55.66 % of cpp submissions

Your memory usage beats 10.86 % of cpp submissions (29.7 MB)

🍅方案一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    struct Node {
        int low_count;
        int val;
        shared_ptr<Node> left, right;
        Node(int val, int count) : 
        low_count(count), val(val), left(nullptr), right(nullptr) {}
        int compareTo(int k) {
            if(val < k) 
                return -1;
            else if (val > k) 
                return 1;
            return 0;
        }
    };
    int Nsize( shared_ptr<Node> h) {
        if(h)
            return h->low_count;
        return 0;
    } 
    shared_ptr<Node> insert(shared_ptr<Node> h, int val) {
        if(!h) 
            return make_shared<Node>(val ,0);
        int cmp = h->compareTo(val);
        if(cmp >= 0) {
            h->left = insert(h->left, val);
        } 
        else if(cmp < 0) {
            h->right = insert(h->right, val);
        } 
        return h;
    }
    int g = 0;
    void rank(shared_ptr<Node> h) {
        if(!h)
            return ;
        if(h->left) 
            rank(h->left);
        h->low_count = g;
        g += 1;
        if(h->right)
            rank(h->right);
    }

    int xx(shared_ptr<Node> h,int val) {
        if(!h)
            return 0;
        while(h) {
            int cmp = h->compareTo(val);
            if(cmp < 0 )
                h = h->right;
            else if(cmp > 0)
                h = h->left;
            else if(cmp == 0 && !h->left)
                break;
            else 
                h = h->left;
        }
        return h->low_count;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> counts(nums.size());
        if(!nums.size())
            return counts;
        counts[0] = 0;
        if(nums.size() == 1) {
            return counts;
        }
        shared_ptr<Node> head = make_shared<Node>(nums.back(), 0);
        for(int i = nums.size() - 2; i >=0 ; -- i){
            head = insert(head, nums[i]);
            g = 0;
            rank(head);
            counts[i] = xx(head, nums[i]);
        }
        return counts;
    }
};

Time Limit Exceeded

15/16 cases passed (N/A)

Testcase
[5183,2271,3067,539,8939,2999,9264,737,3974,5846,-210,9278,5800,2675,6608,1133,-1,6018,9672,5179,9842,7424,-209,2988,2757,5984,1107,2644,-499,7234,7539,6525,347,5718,-742,1797,5292,976,8752,8297,1312,3385,5924,2882,6091,-282,2595,96,1906,8014,7667,5895,7283,7974,-167,7068,3946,6223,189,1589,2058,9277,-302,8157,8256,5261,8067,1071,9470,2682,8197,5632,753,3179,8187,9042,8167,4657,7080,7801,5627,7917,8085,928,-892,-427,3685,4676,2431,8064,8537,343,505,4352,2108,4399,66,2086,1922,9126,9460,393,443,5689,7595,850,8493,2866,732,3738,7933,3666,2370,5804,4045,7903,8009,5387,5542,7593,6862,1547,6934,-160,9693,4560,7429,9989,7232,-594,587,6476,9277,4471,5979,6268,2419,6706,-727,1927,7361,9684,5519,2703,1723…..


 上一页

LeetCode