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 that the given integer.
Example
For array [1,2,7,8,5]
, and queries [1,8,5]
, return [0,4,2]
Note
We suggest you finish problem Segment Tree Build and Segment Tree Query II first.
Challenge
Could you use three ways to do it.
- Just loop
- Sort and binary search
- Build Segment Tree and Search.
Solution: Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>
public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { //Version 1. sort + binary search //Version 2. Segment Tree. not as efficient as version 1. //check <Count of Smaller Number before itself> ArrayList<Integer> result = new ArrayList<>(); if (A == null || queries == null) { return result; } if (A.length == 0) { for (int i = 0; i < queries.length; i++) { result.add(0); } return result; } Arrays.sort(A); for (int i = 0; i < queries.length; i++) { int target = queries[i]; //find the last element A[i]<target, i+1 is the number int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] < target) { start = mid; } else { end = mid; } } if (A[end] < target) { result.add(end + 1); } else if (A[start] < target) { result.add(start + 1); } else { result.add(0); } } return result; }
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 elementAi
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]
We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.
Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。
建一个0-10000的值型线段树。然后每个叶子节点代表这个值的count。所以在A[i]之前比它小的数的个数就是那个0~A[i]-1这个node 的count值。之后每次Query以后把A[i]那个leaf node count++, 相应回溯更新它所有父亲节点。
时间复杂度是O(m + nlogm) m是值的区间,n是query个数。
这个算法是否最优需要分情况,如果值特别分散且query数特别小,那还不如每次query用O(n)的时间count它之前的比她小的数。
public class SegmentTreeNode { int start, end; int count; SegmentTreeNode left; SegmentTreeNode right; public SegmentTreeNode(int start, int end) { this.start = start; this.end = end; this.count = 0; } } public ArrayList<Integer> countOfSmallerNumberII(int[] A) { ArrayList<Integer> result = new ArrayList<>(); if (A == null || A.length == 0) { return result; } SegmentTreeNode node = buildSegmentTree(0, 10000); for (int i = 0; i < A.length; i++) { if (A[i] == 0) { result.add(0); } else { result.add(query(node, 0, A[i] - 1)); } update(node, A[i]); } return result; } public SegmentTreeNode buildSegmentTree(int start, int end) { SegmentTreeNode node = new SegmentTreeNode(start, end); if (start < end) { int mid = start + (end - start) / 2; node.left = buildSegmentTree(start, mid); node.right = buildSegmentTree(mid + 1, end); node.count = node.left.count + node.right.count; } return node; } public int query(SegmentTreeNode node, int start, int end) { if (node.start == start && node.end == end) { return node.count; } int leftCount = 0, rightCount = 0; int mid = node.start + (node.end - node.start) / 2; if (start <= mid) { if (end <= mid) { leftCount = query(node.left, start, end); } else { leftCount = query(node.left, start, mid); } } if (end > mid) { if (start > mid) { rightCount = query(node.right, start, end); } else { rightCount = query(node.right, mid + 1, end); } } return leftCount + rightCount; } public void update(SegmentTreeNode node, int index) { if (node.start == index && node.end == index) { node.count = node.count + 1; } else { int mid = node.start + (node.end - node.start) / 2; if (node.start <= index && index <= mid) { update(node.left, index); } else if (mid < index && index <= node.end) { update(node.right, index); } node.count = node.left.count + node.right.count; //or node.count = node.count+1; } }