给定一个整数数组（下标由 0 到 n-1， n 表示数组的规模，取值范围由 0 到10000）。对于数组中的每个
ai元素，请计算ai前的数中比它小的元素的数量。
注意事项
We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number first.
样例
对于数组
[1,2,7,8,5]，返回[0,1,2,3,2]
思路
原数组中最大值为 max，以 max 为长度建立新的数组，原数组的值为新数组的下标，新数组的值即为原数组值出现的次数，此时求原数组 ai 前数中比它小的元素数量的问题转化为了求新数组区间和的问题，但有一点需要说明，算法要一边查询一边修改，同时进行，因为比如 5 在 7 后面，查询 7 前面的数数量不应该包括 5， 如果先全部修改再查询就会把 5 算上
代码
public class Solution {
/*
* @param A: an integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
public class SegmentTreeNode {
public int start;
public int end;
public int sum;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
this.left = null;
this.right = null;
}
}
public SegmentTreeNode build(int start, int end) {
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);
root.right = build(mid + 1, end);
return root;
}
public int query(SegmentTreeNode root, int start, int end) {
if (start <= root.start && root.end <= end) {
return root.sum;
}
int mid = root.start + (root.end - root.start) / 2;
int ans = 0;
if (start <= mid) {
ans += query(root.left, start, end);
}
if (mid < end) {
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) {
// 此处有个加号，代表每次执行修改操作实际上数组元素出现次数 + 1
// 这也是考虑出现重复元素的情形，比如 [1, 1, 2, 3, 7], 查询 7 前面的元素，1 出现了两次
root.sum += value;
return;
}
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.sum = root.left.sum + root.right.sum;
}
SegmentTreeNode root;
public List<Integer> countOfSmallerNumberII(int[] A) {
root = build(0, 10000);
List<Integer> list = new ArrayList<>();
int res;
for (int i = 0; i < A.length; i++) {
// res 赋值为 0 要在for 中间，如果在 for循环外在 A[i] != 0时没问题
// 但每当 A[i] = 0 时，res 是上一次查询的值，并不是 A[i] = 0 时对应的 0 值
res = 0;
if (A[i] > 0) {
res = query(root, 0 , A[i] - 1);
}
modify(root, A[i], 1);
list.add(res);
}
return list;
}
}
- 写法2
public class Solution {
/**
* @param A: An integer array
* @return: Count the number of element before this element 'ai' is
* smaller than it and return count number array
*/
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 List<Integer> countOfSmallerNumberII(int[] A) {
// write your code here
root = build(0, 10000);
List<Integer> ans = new ArrayList<Integer>();
int res;
for (int i = 0; i < A.length; i++) {
res = 0;
if (A[i] > 0) {
// 查询 A[i] 前面的比它小的元素的数量，所以从 0 查到 A[i] - 1
res = querySegmentTree(root, 0, A[i]-1);
}
modifySegmentTree(root, A[i], 1);
ans.add(res);
}
return ans;
}
}
网友评论