給定一個整數(shù)數(shù)組 （下標(biāo)由 0 到 n-1，其中 n 表示數(shù)組的規(guī)模酿箭，數(shù)值范圍由 0 到 10000），以及一個 查詢列表趾娃。對于每一個查詢缭嫡，將會給你一個整數(shù)，請你返回該數(shù)組中小于給定整數(shù)的元素的數(shù)量抬闷。
注意事項
在做此題前妇蛀，最好先完成 線段樹的構(gòu)造 and 線段樹查詢 II 這兩道題目。
樣例
對于數(shù)組
[1,2,7,8,5]笤成，查詢[1,8,5]评架，返回[0,4,2]
挑戰(zhàn)
可否用一下三種方法完成以上題目。
- 僅用循環(huán)方法
- 分類搜索 和 二進制搜索
- 構(gòu)建 線段樹 和 搜索
思路
整體思路和 249. 統(tǒng)計前面比自己小的數(shù)的個數(shù) 相似炕泳，區(qū)別在于本題是數(shù)組中的所有小于給定數(shù)的數(shù)的個數(shù)纵诞，而另一題是求數(shù)組中在給定數(shù)前面所有小于給定數(shù)的數(shù)的個數(shù)，上一題要一邊 modify 一邊 query培遵，本題可以先把所有數(shù) modify浙芙，再 query
注意
構(gòu)造線段樹的時間復(fù)雜度為 O(N)，查詢時間復(fù)雜度為 O(logN)籽腕，更新的時間復(fù)雜度為 O(logN)
代碼
- 線段樹的無需手動拆分區(qū)間寫法
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;
}
}
- 線段樹的手動拆分區(qū)間寫法
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;
// 左子區(qū)
if(start <= mid) {
if( mid < end) { // 分裂
leftcount = querySegmentTree(root.left, start, mid);
} else { // 包含
leftcount = querySegmentTree(root.left, start, end);
}
}
// 右子區(qū)
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;
}
}
- 二分法嗡呼， 時間復(fù)雜度： O((N + K)*logN)， N == A.length皇耗， K == queries.length南窗，NlogN 將數(shù)組排序，然后查找 K 個數(shù)郎楼，每個數(shù)查找所需時間 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;
}
}
