Tuesday, May 7, 2019

Lintcode 248. Count of Smaller Number

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller than the given integer.

Example

Example 1:
Input: array =[1,2,7,8,5] queries =[1,8,5]
Output:[0,4,2]
Example 2:
Input: array =[3,4,5,8] queries =[2,4]
Output:[0,1]

Challenge

Could you use three ways to do it.
  1. Just loop
  2. Sort and binary search
  3. Build Segment Tree and Search.

Notice


Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class Solution {
    /**
     * @param A: An integer array
     * @param queries: The query list
     * @return: The number of element in the array that are smaller that the given integer
     */
    public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (queries == null || queries.length == 0) {
            return ans;
        }
         
        // step 1: build a segment tree
        SegmentTree segmentTree = new SegmentTree(A);
 
        // step 2; query the segment tree
        for (int query : queries) {
            int count = segmentTree.query(0, query - 1);
            ans.add(count);
        }
 
        return ans;
    }
}
 
class SegmentTree {
    private SegmentTreeNode root = null;
 
    public SegmentTree(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
         
        Map<Integer, Integer> numToCount = new HashMap<>();
        for (int num : A) {
            int count = numToCount.getOrDefault(num, 0);
            count += 1;
            numToCount.put(num, count);
        }
 
        root = buildSegmentTree(0, 10000, numToCount);
    }
 
    public int query(int start, int end) {
        return queryHelper(root, start, end);
    }
 
    private int queryHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || start > end) {
            return 0;
        }
 
        if (start == root.start && end == root.end) {
            return root.count;
        }
 
        int mid = root.start + (root.end - root.start) / 2;
        int leftCount = queryHelper(root.left, Math.max(start, root.start), Math.min(end, mid));
        int rightCount = queryHelper(root.right, Math.max(mid + 1, start), Math.min(root.end, end));
 
        return leftCount + rightCount;
    }
 
    private SegmentTreeNode buildSegmentTree(int start, int end, Map<Integer, Integer> numToCountMap) {
        if (start > end) {
            return null;
        }
 
        if (start == end) {
            int count = numToCountMap.getOrDefault(start, 0);
            return new SegmentTreeNode(start, end, count);
        }
 
        int mid = start + (end - start) / 2;
        SegmentTreeNode leftChild = buildSegmentTree(start, mid, numToCountMap);
        SegmentTreeNode rightChild = buildSegmentTree(mid + 1, end, numToCountMap);
 
        SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.count + rightChild.count);
        root.left = leftChild;
        root.right = rightChild;
 
        return root;
    }
 
}
 
class SegmentTreeNode {
    int start, end;
    int count;
    SegmentTreeNode left, right;
 
    public SegmentTreeNode(int start, int end, int count) {
        this.start = start;
        this.end = end;
        this.count = count;
        left = right = null;
    }
}
Another solution from Jiuzhang:
Build an empty segment tree first, with all count zero. Then update the tree with the new value.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/
 
public class Solution {
   /**
     * @param A: An integer array
     * @return: The number of element in the array that
     *          are smaller that the given integer
     */
    class SegmentTreeNode {
        public int start, end;
        public int count;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int start, int end, int count) {
              this.start = start;
              this.end = end;
              this.count = count;
              this.left = this.right = null;
        }
    }
    SegmentTreeNode root;
    public SegmentTreeNode build(int start, int end) {
        // write your code here
        if(start > end) {  // check core case
            return null;
        }
         
        SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
         
        if(start != end) {
            int mid = (start + end) / 2;
            root.left = build(start, mid);
            root.right = build(mid+1, end);
        } else {
            root.count =  0;
        }
        return root;
    }
    public int querySegmentTree(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(start == root.start && root.end == end) { // 相等
            return root.count;
        }
         
         
        int mid = (root.start + root.end)/2;
        int leftcount = 0, rightcount = 0;
        // 左子区
        if(start <= mid) {
            if( mid < end) { // 分裂
                leftcount =  querySegmentTree(root.left, start, mid);
            } else { // 包含
                leftcount = querySegmentTree(root.left, start, end);
            }
        }
        // 右子区
        if(mid < end) { // 分裂 3
            if(start <= mid) {
                rightcount = querySegmentTree(root.right, mid+1, end);
            } else { //  包含
                rightcount = querySegmentTree(root.right, start, end);
            }
        } 
        // else 就是不相交
        return leftcount + rightcount;
    }
    public void modifySegmentTree(SegmentTreeNode root, int index, int value) {
        // write your code here
        if(root.start == index && root.end == index) { // 查找到
            root.count += value;
            return;
        }
         
        // 查询
        int mid = (root.start + root.end) / 2;
        if(root.start <= index && index <=mid) {
            modifySegmentTree(root.left, index, value);
        }
         
        if(mid < index && index <= root.end) {
            modifySegmentTree(root.right, index, value);
        }
        //更新
        root.count = root.left.count + root.right.count;
    }
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        // write your code here
        root = build(0, 10000);
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int res;
        for(int i = 0; i < A.length; i++) {
            modifySegmentTree(root, A[i], 1);
        }
        for(int i = 0; i < queries.length; i++) {
            res = 0;
            if(queries[i] > 0)
                res = querySegmentTree(root, 0, queries[i] - 1);
            ans.add(res);
        }
        return ans;
    }
}

Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)