315.Count of Smaller Numbers After Self My Submissions Question

You are given an integer array nums and you have to return a new counts array. Thecounts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).

To the right of 2 there is only 1 smaller element (1).

To the right of 6 there is 1 smaller element (1).

To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Subscribe to see which companies asked this question

因为需要求某元素右边小于该元素的数组元素的个数，所以从数组末尾开始向前进行处理。数据结构使用树，节点有属性value，smaller，分别表示对应元素的值以及数组中小于该元素值的个数。函数insert既向树种插入新的节点，又能够求得数组右边小于value的元素的个数。因为数组末尾的元素的smaller值首先返回，所以要用到双向队列deque，将每次求得的值插入链表的头部。最终返回整个队列的值即可。

在插入操作中，请注意函数的参数root是指针的引用，因为对该指针的修改必须得到保留。如果root为空（代表数组末尾的那个元素），初始化根节点，返回0.如果根节点的值大于value，需要把这个元素对应的几点向左插入树中，同时，小于根节点的值的元素个数加1.剩余的情况下，节点需要向右插入树中，返回的值应该是比root节点小的元素个数加上树的右半部分比该元素小的元素个数，同时还要区分一下要插入的值是大于还是等于root节点的值。

很精妙的解法，真是只可意会，不可言传啊。

class Solution {

private:

    class Node{

    public:

        int value;

        int smaller;

        Node *left;

        Node *right;

        Node(int value,int smaller) {

            this ->value = value;

            this ->smaller =smaller;

            left=right=NULL;//在leetcode中，必须要加上这句，否则超时

        }

    };

    int insert(Node * & root,int value){

        if(root ==NULL){

            root =new Node(value,);

            return ;

        }

        if(root->value > value){

            root->smaller++;

            return insert(root->left,value);

        }

        return root->smaller+insert(root->right,value)+(root->value <value? :);

    }

public:

    vector<int> countSmaller(vector<int>& nums) {

        Node * root=NULL;

        deque <int >q;

        for(int i=nums.size()-;i>-;i-- ){

            int value =insert(root,nums[i]);

            cout<<"this is a test! "<<value<<endl;

            q.push_front(value);

        }

        return vector<int>(q.begin(),q.end());

    }

};

巴特西

315.Count of Smaller Numbers After Self My Submissions Question

最新文章

热门文章