题目

count-of-smaller-numbers-after-self

算法

* 二分查找

* 插入排序

* 二叉查找树

代码

* 二分查找

// Binary Search

class Solution {

public:

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

        vector<int> t, res(nums.size());

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

            int left = 0, right = t.size();

            while (left < right) {

                int mid = left + (right - left) / 2;

                if (t[mid] >= nums[i]) right = mid;

                else left = mid + 1;

            }

            res[i] = right;

            t.insert(t.begin() + right, nums[i]);

        }

        return res;

    }

};

* 插入排序

// Insert Sort

class Solution {

public:

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

        vector<int> t, res(nums.size());

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

            int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));

            res[i] = d;

            t.insert(t.begin() + d, nums[i]);

        }

        return res;

    }

};

* 二叉查找树

// Binary Search Tree

class Solution {

public:

    struct Node {

        int val, smaller;

        Node *left, *right;

        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}

    };

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

        if (!root) return (root = new Node(v, 0)), 0;

        if (root->val > v) return root->smaller++, insert(root->left, v);

        else return insert(root->right, v) + root->smaller + (root->val < v ? 1 : 0);

    }

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

        vector<int> res(nums.size());

        Node *root = NULL;

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

            res[i] = insert(root, nums[i]);

        }

        return res;

    }

};