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.
- Just loop
- Sort and binary search
- Build Segment Tree and Search.
Notice
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.
/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，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;
}
}
No comments:
Post a Comment