Massive Algorithms: Techinpad: [LintCode] Count of Smaller Number before itself

Techinpad: [LintCode] Count of Smaller Number before itself

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

X. Segment tree
https://xmruibi.gitbooks.io/interview-preparation-notes/content/Algorithm/SegmentTree/CountSmallerNumBeforeItself.html

Segment Tree
Initial with the range (0 to 10000)
Count array elements included in a certain tree node
Dynamic count and make a query.
- Query a value, evaluate the value and node's middle value,
- if larger, that means the left node's count should be included and also enter into the right node;
- if less, just enter the left node;
- recursive until touch the null node;

https://helloyuantechblog.wordpress.com/2015/12/17/lintcode-count-of-smaller-number-before-itself-hard/
http://techinpad.blogspot.com/2015/05/lintcode.html

      class SegmentTreeNode {
      public:
          int start, end, count;
          SegmentTreeNode *left, *right;
          SegmentTreeNode(int start, int end, int count) {
              this->start = start;
              this->end = end;
              this->count = count;
              this->left = this->right = NULL;
          }
      };

   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */
    SegmentTreeNode *buildLeft(int start, int end)
    {
        SegmentTreeNode *node = new SegmentTreeNode(start, end, 1);
        if(start == end) return node;
        node->left = new SegmentTreeNode(start, start, 1);
        node->right = new SegmentTreeNode(start+1, end, 0);
        return node;
    }
    
    int update(SegmentTreeNode *&node, int val)
    {
        if(val > node->end)
        {
            int res = node->count;
            SegmentTreeNode *head = new SegmentTreeNode(node->start, 
                                                 val, node->count+1);
            head->right = new SegmentTreeNode(node->end+1, val, 1);
            head->left = node;
            node = head;
            return res;
        }
        if(val < node->start)
        {
            SegmentTreeNode *head = new SegmentTreeNode(val, 
                              node->end, node->count+1);
            head->left = buildLeft(val, node->start-1);
            head->right = node;
            node = head;
            return 0;
        }
        node->count ++;
        if(node->left)
        {
            if(node->left->end >= val) return update(node->left, val);
            return update(node->right, val) + node->left->count;
        }
        else
        {
            node->left = new SegmentTreeNode(node->start, val, 1);
            node->right = new SegmentTreeNode(val+1, node->end, 
                                                   node->count);
        }
        return 0;
    }
    vector<int> countOfSmallerNumberII(vector<int> &A) {
        // write your code here
        int len = A.size();
        vector<int> res(len,0);
        if(0 == len)return res;
        SegmentTreeNode * root = new SegmentTreeNode(A[0], A[0], 1);
        for(int i=1;i<len;i++)
        {
            res[i] = update(root, A[i]);
        }
        return res;
    }

https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/segment_tree/count_of_smaller_number_before_itself.html
http://www.jianshu.com/p/a2aae061d637
https://github.com/shawnfan/LintCode/blob/master/Java/Count%20of%20Smaller%20Number%20before%20itself.java

  public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
    ArrayList<Integer> result = new ArrayList<>();
    SegmentTreeNode root = buildSegmentTree(0, 10000);
    for (int num : A) {
      modifySegmentTree(root, num, 1);
      result.add(querySegmentTree(root, 0, num - 1));  // range: [0, query - 1]
    }
    return result;
  }

  private SegmentTreeNode buildSegmentTree(int start, int end) {
    if (start > end) {
      return null;
    } else if (start == end) {
      return new SegmentTreeNode(start, end);
    }
    SegmentTreeNode root = new SegmentTreeNode(start, end);
    int mid = start + (end - start) / 2;
    root.left = buildSegmentTree(start, mid);
    root.right = buildSegmentTree(mid + 1, end);
    return root;
  }

  private void modifySegmentTree(SegmentTreeNode root, int num, int count) {
    if (root == null || num > root.end || num < root.start) {
      return ;
    } 
    if (root.start == num && root.end == num) {
      root.count = count;
      return;
    }
    modifySegmentTree(root.left, num, count);
    modifySegmentTree(root.right, num, count);
    int leftCount = root.left == null ? 0 : root.left.count;
    int rightCount = root.right == null ? 0 : root.right.count;
    root.count = leftCount + rightCount;
  }

  private int querySegmentTree(SegmentTreeNode root, int start, int end) {
    if (root == null || start > root.end || end < root.start) {
      return 0;
    }
    if (root.start >= start && root.end <= end) {
      return root.count;
    }
    return querySegmentTree(root.left, start, end) + querySegmentTree(root.right, start, end);
  }

  class SegmentTreeNode {
    int start;
    int end;
    int count;  // default value 0
    SegmentTreeNode left;
    SegmentTreeNode right;

    public SegmentTreeNode(int start, int end) {
      this.start = start;
      this.end = end;
    }
  }

https://codesolutiony.wordpress.com/2015/05/12/lintcode-count-of-smaller-number-before-itself/

    public ArrayList<Integer> countOfSmallerNumberII(int[] A) {

        ArrayList<Integer> res = new ArrayList<Integer>();

        if (A == null || A.length == 0) {

            return res;

}

        MaxTreeNode root = build(A, 0, A.length - 1);

        for (int i = 0; i < A.length; i++) {

            res.add(getVal(root, i, A[i]));

}

        return res;

}

    private int getVal(MaxTreeNode root, int end, int val) {

        if (root == null || root.start > end) {

            return 0;

}

        if (root.start == root.end || root.end >= end) {

            if (root.max < val)

                return root.end - root.start + 1;

}

        return getVal(root.left, end, val) + getVal(root.right, end, val);

}

    private MaxTreeNode build(int[] a, int start, int end) {

        if (start > end) {

            return null;

}

        if (start == end) {

            return new MaxTreeNode(start, start, a[start]);

}

        MaxTreeNode root = new MaxTreeNode(start, end);

        root.left = build(a, start, (start + end) / 2);

        root.right = build(a, (start + end) / 2 + 1, end);

        int max = 0;

        if (root.left == null) {

            root.max = root.right.max;

        } else if (root.right == null) {

            root.max = root.left.max;

        } else {

            root.max = Math.max(root.left.max, root.right.max);

}

        return root;

}

    class MaxTreeNode {

        int start;

        int end;

        int max;

        MaxTreeNode left;

        MaxTreeNode right;

        public MaxTreeNode(int start, int end) {

            this.start = start;

            this.end = end;

}

        public MaxTreeNode(int start, int end, int max) {

            this(start, end);

            this.max = max;

}

}

http://techinpad.blogspot.com/2015/05/lintcode.html
https://github.com/LloydSSS/LintCode-LeetCode/blob/master/count-of-smaller-number-before-itself.cpp

class SegmentTreeNode {
public:
int start, end, count;
SegmentTreeNode *left, *right;
SegmentTreeNode(int start, int end, int count) {
this->start = start;
this->end = end;
this->count = count;
this->left = this->right = NULL;
}
};
/**
* @param A: An integer array
* @return: Count the number of element before this element 'ai' is
* smaller than it and return count number array
*/
SegmentTreeNode *buildLeft(int start, int end)
{
SegmentTreeNode *node = new SegmentTreeNode(start, end, 1);
if(start == end) return node;
node->left = new SegmentTreeNode(start, start, 1);
node->right = new SegmentTreeNode(start+1, end, 0);
return node;
}
int update(SegmentTreeNode *&node, int val)
{
if(val > node->end)
{
int res = node->count;
SegmentTreeNode *head = new SegmentTreeNode(node->start,
val, node->count+1);
head->right = new SegmentTreeNode(node->end+1, val, 1);
head->left = node;
node = head;
return res;
}
if(val < node->start)
{
SegmentTreeNode *head = new SegmentTreeNode(val,
node->end, node->count+1);
head->left = buildLeft(val, node->start-1);
head->right = node;
node = head;
return 0;
}
node->count ++;
if(node->left)
{
if(node->left->end >= val) return update(node->left, val);
return update(node->right, val) + node->left->count;
}
else
{
node->left = new SegmentTreeNode(node->start, val, 1);
node->right = new SegmentTreeNode(val+1, node->end,
node->count);
}
return 0;
}
vector<int> countOfSmallerNumberII(vector<int> &A) {
// write your code here
int len = A.size();
vector<int> res(len,0);
if(0 == len)return res;
SegmentTreeNode * root = new SegmentTreeNode(A[0], A[0], 1);
for(int i=1;i<len;i++)
{
res[i] = update(root, A[i]);
}
return res;
}

X. Binary Index Tree
http://www.cnblogs.com/easonliu/p/4575645.html

题目让用线段树，其实树状数组就能搞定，而且树状数组的代码太短小精悍了。

8     int lowbit(int n) {
 9         return n & (-n);
10     }
11     
12     int sum(vector<int> &c, int n) {
13         int sum = 0;
14         while (n > 0) {
15             sum += c[n];
16             n -= lowbit(n);
17         }
18         return sum;
19     }
20     
21     void add(vector<int> &c, int i, int x) {
22         while (i < c.size()) {
23             c[i] += x;
24             i += lowbit(i);
25         }
26     }
27     
28     vector<int> countOfSmallerNumberII(vector<int> &A) {
29         // write your code here
30         vector<int> c(10002, 0);
31         vector<int> res(A.size());
32         for (int i = 0; i < A.size(); ++i) {
33             res[i] = sum(c, A[i]);
34             add(c, A[i] + 1, 1);
35         }
36         return res;
37     }

如果有负数或者数特别大的话，可以先离散化一下再搞。

28     vector<int> countOfSmallerNumberII(vector<int> &A) {
29         // write your code here
30         vector<int> c(A.size() + 1, 0);
31         vector<int> res(A.size()), B(A);
32         map<int, int> mp;
33         sort(B.begin(), B.end());
34         for (int i = 0; i < B.size(); ++i) {
35             mp[B[i]] = i + 1;
36         }
37         for (int i = 0; i < A.size(); ++i) {
38             res[i] = sum(c, mp[A[i]] - 1);
39             add(c, mp[A[i]], 1);
40         }
41         return res;
42     }

https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/segment_tree/count_of_smaller_number_before_itself.html

Similar as http://www.geeksforgeeks.org/count-smaller-elements-on-right-side/
Read full article from Techinpad: [LintCode] Count of Smaller Number before itself

Techinpad: [LintCode] Count of Smaller Number before itself

Labels

Popular Posts