(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 that the given integer.
http://ying.ninja/?p=775
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>
Solution 2: Segment tree
http://www.tangjikai.com/algorithms/lintcode-248-count-of-smaller-number
O(n+mlogn) time (m queries, n segment tree nodes)
O(logn) space
Solution 1: binary search
https://xmruibi.gitbooks.io/interview-preparation-notes/content/Algorithm/BinarySearch/CountSmallerNumber.html
1. Solution by Loop with O(n^2)
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]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;}http://www.tangjikai.com/algorithms/lintcode-248-count-of-smaller-number
O(n+mlogn) time (m queries, n segment tree nodes)
O(logn) space
class SegmentTreeNode:
def __init__(self, start, end, count):
self.start, self.end, self.count = start, end, count
self.left, self.right = None, None
"""
@param A: A list of integer
@return: The number of element in the array that
are smaller that the given integer
"""
def countOfSmallerNumber(self, A, queries):
# write your code here
# build segmeng tree
root = self.build(0, 10000)
ans = []
# modify count value for each
for i in A:
self.modify(root, i, 1)
for i in queries:
res = 0
if i > 0:
res = self.query(root, 0, i - 1)
ans.append(res)
return ans
def build(self, start, end):
if start >= end:
return SegmentTreeNode(start, end, 0)
mid = start + (end - start) / 2
l = self.build(start, mid)
r = self.build(mid+1, end)
root = SegmentTreeNode(start, end, 0)
root.left = l
root.right = r
return root
def modify(self, root, index, value):
if root.start == index and root.end == index:
root.count += value
return
# query
mid = root.start + (root.end - root.start) / 2
if root.start <= index <= mid:
self.modify(root.left, index, value)
if mid < index <= root.end:
self.modify(root.right, index, value)
root.count = root.left.count + root.right.count
def query(self, root, start, end):
if start == root.start and end == root.end:
return root.count
mid = root.start + (root.end - root.start) / 2
lCount = rCount = 0
if start <= mid:
if end > mid:
lCount = self.query(root.left, start, mid)
else:
lCount = self.query(root.left, start, end)
if end > mid:
if start <= mid:
rCount = self.query(root.right, mid+1, end)
else:
rCount = self.query(root.right, start, end)
return lCount + rCount public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { ArrayList<Integer> res = new ArrayList<Integer>(); if (A == null || queries == null || queries.length == 0) { return res; } Arrays.sort(A); MaxNode root = buildTree(A, 0, A.length - 1); for (int q : queries) { res.add(query(A, root, q)); } return res; } private MaxNode buildTree(int[] A, int start, int end) { if (start > end) { return null; } MaxNode root = new MaxNode(start, end); if (start == end) { root.val = A[start]; } else { root.left = buildTree(A, start, (start+end)/2); root.right = buildTree(A, (start+end)/2+1, end); root.val = root.left == null ? root.right.val : Math.max(root.left.val, root.right == null ? 0 : root.right.val); } return root; } private int query(int[] A, MaxNode root, int val) { if (root == null || A[root.start] > val) { return 0; } if (root.val < val) { return root.end - root.start + 1; } return query(A, root.left, val) + query(A, root.right, val); } class MaxNode { int start; int end; int val; //how many nodes are between the range start - end (inclusive) MaxNode left; MaxNode right; public MaxNode() { } public MaxNode(int start, int end) { this.start = start; this.end = end; } public MaxNode(int start, int end, int val) { this(start, end); this.val = val; } } public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { Arrays.sort(A); ArrayList<Integer> res = new ArrayList<Integer>(); for (int q : queries) { res.add(binarySearch(A, q)); } return res; } private int binarySearch(int[] A, int val) { int start = 0, end = A.length - 1; int res = 0; while (start <= end) { int mid = (start + end) / 2; if (A[mid] >= val) { end = mid - 1; } else { res = mid + 1; start = mid + 1; } } return res; }1. Solution by Loop with O(n^2)
public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
ArrayList<Integer> res = new ArrayList<>();
if(A == null || queries == null)
return res;
for(int i = 0; i < queries.length; i++) {
int cnt = 0;
for(int j = 0; j < A.length; j++) {
if(A[j] < queries[i])
cnt++;
}
res.add(cnt);
}
return res;
}