315 Count of Smaller Numbers After Self
Problem:
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
Solutions:
Binary search insert
public class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new LinkedList<Integer>();
ArrayList<Integer> cand = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i --) {
int left = 0, right = cand.size();
while(left < right) {
int mid = (right - left) / 2 + left;
if (cand.get(mid) < nums[i]) {
left = mid + 1;
}
else {
right = mid;
}
}
result.add(0, right);
cand.add(right, nums[i]);
}
return result;
}
}
Binary Search Tree
public class Solution {
private class Node {
public int val;
public int cnt;
public int leftSum;
public Node left;
public Node right;
public Node(int val) {
cnt = 1;
leftSum = 0;
this.val = val;
}
}
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new LinkedList<>();
Node root = null;
for(int i = nums.length - 1; i >= 0; i --) {
root = helper(res, nums[i], root, 0);
}
return res;
}
private Node helper(List<Integer> res, int val, Node root, int preNum) {
if(root == null) {
res.add(0, preNum);
return new Node(val);
}
if(root.val == val) {
root.cnt ++;
res.add(0, preNum + root.leftSum);
}
else if(root.val > val) {
root.leftSum ++;
root.left = helper(res, val, root.left, preNum);
}
else {
root.right = helper(res, val, root.right, preNum + root.leftSum + root.cnt);
}
return root;
}
}
Binary Indexed tree
public class Solution {
public List<Integer> countSmaller(int[] nums) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i ++) {
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
int diff = 1 - min;
for (int i = 0; i < nums.length; i ++) {
nums[i] += diff;
}
max += diff;
List<Integer> result = new LinkedList<Integer>();
int[] sums = new int[max + 1];
for (int i = nums.length - 1; i >= 0; i --) {
result.add(0, getSum(sums, nums[i] - 1));
update(sums, nums[i]);
}
return result;
}
private int getSum(int[] sums, int index) {
int sum = 0;
while (index > 0) {
sum += sums[index];
index -= index & (-index);
}
return sum;
}
private void update(int[] sums, int val) {
while (val < sums.length) {
sums[val] += 1;
val += val&(-val);
};
}
}