lintcode-统计前面比自己小的数的个数

给定一个整数数组（下标由 0 到 n-1， n 表示数组的规模，取值范围由 0 到10000）。对于数组中的每个 ai 元素，请计算 ai 前的数中比它小的元素的数量。

分析：求ai前的数中比他小的元素数量，即，在ai之前的元素中区间[0, ai-1]的元素数量

构建线段树，节点中包含元素出现的次数，所有count>0 的叶子结点表示元素存在；依次更新结点计数，所以后面的元素不影响前面的元素计数。

class Node {
    public:
        int start, end, count;
        Node * left, * right;
        Node(int start, int end){
            this->start = start;
            this->end = end;
            this->left = this->right = NULL;
            this->count = 0;
        }
};
class Solution {
public:
   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */
     
    Node * build(int start, int end) {
        if(start > end) {
            return NULL;
        }
        
        Node * root  = new Node(start, end);
    
        if(start < end) {
            int mid = (start+end)>>1;
            root->left = build(start, mid);
            root->right = build(mid+1, end);
        }
    
        return root;
    } 
    
    int query(Node * root, int start, int end) {
        if(root == NULL) {return 0;}
        if(start > end || root->start > end || root->end < start) { return 0; }
        
        if(start <= root->start && end >= root->end) {return root->count; }
        
        int mid = (root->start + root->end) >> 1;
        
        int leftCount = query(root->left, start, min(mid, end));
        int rightCount = query(root->right, max(mid, start), end);
        
        return leftCount + rightCount;
    }
    
    void insert(Node * root, int value) {
        if(root == NULL) {return; }
        if(root->start == root->end && root->start == value) {
            root->count += 1; 
            return;   //注意
            
        }
        int mid = (root->start + root->end) >> 1;
        
        if(value <= mid) {
            insert(root->left, value);
        } else {
            insert(root->right, value);
        }
        
        //回溯，自下而上更新count
        //root->left一定存在，root->right不一定存在。需要判断
        root->count = root->left->count + (root->right ? root->right->count : 0);
        
    }
     
    vector<int> countOfSmallerNumberII(vector<int> &A) {
        // write your code here
        
        Node * root = build(0, 10005);
        vector<int> ret;
        for(int i = 0;i < A.size(); ++i) {
            int cnt = query(root, 0, A[i]-1);
            ret.push_back(cnt);
            insert(root, A[i]);
        }
        
        return ret;
    }
};

二分查找法(超时)

lower_bound(A.begin(), A.end(), value); 使用二分查找法返回有序区间中第一个大于或等于value的位置

class Solution {
public:
   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */
    vector<int> countOfSmallerNumberII(vector<int> &A) {
        // write your code here
        vector<int> ret;
        vector<int>::iterator it;
        for(it = A.begin(); it != A.end(); ++it) {
            vector<int> tmp(A.begin(), it);
            sort(tmp.begin(), tmp.end());
            int cnt = lower_bound(tmp.begin(), tmp.end(), (*it)) - tmp.begin();
            ret.push_back(cnt);
        }
        
        return ret;
    }
};