給定一個整數數組（下標由 0 到 n-1， n 表示數組的規模，取值范圍由 0 到10000）。對于數組中的每個?ai?元素，請計算?ai?前的數中比它小的元素的數量。

?注意事項

We suggest you finish problem?Segment Tree Build,?Segment Tree Query II?and?Count of Smaller Number?first.

樣例

對于數組[1,2,7,8,5]?，返回?[0,1,2,3,2]

解題思路：

　　題目提示我們使用線段樹，在這里我寫了兩種線段樹的解法，一種TLE，一種正常通過；個人感覺兩種寫法需要因地制宜使用：

?

　　思路1：每個線段樹節點存儲的是原始vector的index前后值以及該區間內的相應最大值，在查詢時，通過區域以及最大值約束找到所有小于特定值的區間最后求和。

class SegmentTreeNode{	//線段樹節點，其中max是當前區域內（left-right）最大值
public:int start,end,max;SegmentTreeNode2 * left;SegmentTreeNode2 * right;SegmentTreeNode2(int x,int y,int max){this->start = x;this->end = y;this->max = max;this->left = this->right = nullptr;}
};class Solution {
public:/*** @param A: an integer array* @return: A list of integers includes the index of the first number and the index of the last number*/vector<int> countOfSmallerNumberII(vector<int> &A) {// write your code hereauto tree = new SegmentTreeNode(0,A.size()-1,INT_MIN);buildTree(A,tree);vector<int> ret;for(int i = 0;i<A.size();++i){ret.push_back(query(tree,0,i,A[i]));}return ret;}int buildTree(vector<int> &A,SegmentTreeNode * root){	//建立線段樹，每個節點保存該區域內最大值int start = root->start;int end = root->end;if(start > end) return 0;if(start == end) {root->max = A[start];return A[start];}else{root->left = new SegmentTreeNode(start,(start+end)/2,INT_MIN);root->right = new SegmentTreeNode((start+end)/2+1,end,INT_MIN);int L_max = buildTree(A,root->left);int R_max = buildTree(A,root->right);root->max = L_max>R_max?L_max:R_max;return root->max;};}int query(SegmentTreeNode * root,int start,int end,int q){	//查詢特定區域比q小的個數if(root == nullptr) return 0;if(root->start > end || root->end < start) return 0;if(root->start >= start && root->end <= end && root->max<q) return root->end - root->start + 1;return query(root->left,start,end,q)+query(root->right,start,end,q);}
};

　　這種解法TLE，時間復雜度在vector的size很大時很大，某種程度上來講效率不及直接暴力法，但當所求數據較為集中時應該能提高一點速度。

?

思路2：對數據的區間建立線段樹，在知道所有數據上界的情況下效率不錯，能夠正常通過

class SegmentTreeNode{//count表示當前區間所有的數個數
public:int start,end,count;SegmentTreeNode * left;SegmentTreeNode * right;SegmentTreeNode(int x,int y,int count){this->start = x;this->end = y;this->count = count;this->left = this->right = nullptr;}
};class Solution {
public:/*** @param A: an integer array* @return: A list of integers includes the index of the first number and the index of the last number*/vector<int> countOfSmallerNumberII(vector<int> &A) {// write your code herevector<int> res;SegmentTreeNode * root = buildTree(0,10001);for(int i=0; i<A.size(); ++i){res.push_back(query(root,A[i]));insert(root,A[i]);}return res;}SegmentTreeNode* buildTree(int start,int end){  //這種方法需要明確數據上界，然后直接根據數據大小建立線段樹，每個節點保存落在當前區間數的個數if(start > end) return nullptr;auto res = new SegmentTreeNode(start,end,0);if(start == end) return res;int mid = (start+end)/2;res->left = buildTree(start,mid);res->right = buildTree(mid+1,end);return res;}int query(SegmentTreeNode * root,int q){   //query函數用來查詢當前區域內小于q的數的個數if(root == nullptr) return 0;if(q < root->start) return 0;if(q > root->end) return root->count;return query(root->left,q)+query(root->right,q);}void insert(SegmentTreeNode * root,int val){//將輸入數據逐個插入，從上到下逐個更新countif(root == nullptr) return;if(root->start > val || root->end < val) return;if(root->start <= val && root->end >= val) ++root->count;insert(root->left,val);insert(root->right,val);}
}

　　ps:這道題如果使用lintcode內置的SegmentTreeNode 數據結構中的count好像會出問題，最好定義自己的class

?

轉載于:https://www.cnblogs.com/J1ac/p/8729389.html

總結

以上是生活随笔為你收集整理的LintCode 249. 统计前面比自己小的数的个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。