给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。
注意事项
样例
对于数组
[1,2,7,8,5]，查询[1,8,5]，返回[0,4,2]
挑战
可否用一下三种方法完成以上题目。
- 仅用循环方法
- 分类搜索 和 二进制搜索
- 构建 线段树 和 搜索
思路
整体思路和 249. 统计前面比自己小的数的个数 相似，区别在于本题是数组中的所有小于给定数的数的个数，而另一题是求数组中在给定数前面所有小于给定数的数的个数，上一题要一边 modify 一边 query，本题可以先把所有数 modify，再 query
注意
构造线段树的时间复杂度为 O(N)，查询时间复杂度为 O(logN)，更新的时间复杂度为 O(logN)
代码
- 线段树的无需手动拆分区间写法
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
*/
class SegmentTreeNode {
public int start;
public int end;
public int count;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end, int count) {
this.start = start;
this.end = end;
this.count = count;
this.left = null;
this.right = null;
}
}
public SegmentTreeNode build(int start, int end, int[] A) {
if (start > end) {
return null;
}
if (start == end) {
return new SegmentTreeNode(start, end, 0);
}
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
int mid = start + (end - start) / 2;
root.left = build(start, mid, A);
root.right = build(mid + 1, end, A);
if (root.left != null) {
root.count += root.left.count;
}
if (root.right != null) {
root.count += root.right.count;
}
return root;
}
public int query(SegmentTreeNode root, int start, int end) {
if (start <= root.start && root.end <= end) {
return root.count;
}
int mid = root.start + (root.end - root.start) / 2;
int ans = 0;
if (start <= mid) {
ans += query(root.left, start, end);
}
if (end > mid) {
ans += query(root.right, start, end);
}
return ans;
}
public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == root.end && root.start == index) {
root.count += value;
// 没有 return 就会抛出空指针异常
return;
}
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
}
if (index > mid) {
modify(root.right, index, value);
}
root.count = root.left.count + root.right.count;
}
SegmentTreeNode root;
public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
root = build(0, 10000, A);
for (int i = 0; i < A.length; i++) {
modify(root, A[i], 1);
}
List<Integer> array = new ArrayList<>();
int res;
for (int i = 0; i < queries.length; i++) {
res = 0;
if (queries[i] > 0) {
res = query(root, 0, queries[i] - 1);
}
array.add(res);
}
return array;
}
}
- 线段树的手动拆分区间写法
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;
}
}
- 二分法， 时间复杂度： O((N + K)*logN)， N == A.length， K == queries.length，NlogN 将数组排序，然后查找 K 个数，每个数查找所需时间 logN
public class Solution {
public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
if (queries == null || queries.length == 0) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<>(queries.length);
int lenA = (A == null) ? 0 : A.length;
Arrays.sort(A);
for (int query : queries) {
if (lenA == 0) {
ans.add(0);
} else {
ans.add(binarySearch(A, query));
}
}
return ans;
}
private int binarySearch(int[] A, int target) {
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 (target <= A[start]) {
return start;
}
if (target <= A[end]) {
return end;
}
return end + 1;
}
}
