315. Count of Smaller Numbers After Self (Hard)
https://leetcode.com/problems/count-of-smaller-numbers-after-self/
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:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.
Solutions
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
List<Integer> sorted = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
int index = insert(sorted, nums[i]);
ans.add(0, index);
}
return ans;
}
private int insert(List<Integer> sorted, int target) {
if (sorted.size() == 0) {
sorted.add(target);
return 0;
}
int left = 0;
int right = sorted.size() - 1;
// Do not forget the equal numbers
if (sorted.get(left) >= target) {
sorted.add(0, target);
return 0;
}
if (sorted.get(right) < target) {
sorted.add(target);
return right + 1;
}
// [1,3,3], 3, left 0, right 2
// [1,3,5,7], 3, left 0, right 4
// [1,1,1,3,3], 3, left 0, right 4
while (left < right) {
// No need to take account of overflow issue
int mid = (right + left) / 2; // mid=1
if (sorted.get(mid) < target) {
left = mid + 1;
}
// sorted.get(mid) 3 >= target 3,
else {
right = mid - 1; // right=1-1=0
}
}
// to reach here, left == right or left - right == 1
// mid==left, and right=mid-1
// [xxx, 1,3,4], left points to 1, right points to 3, insert after 1, left+1
// [xxx, 1,3,4], left points to 3, left points to 4, edge off 3, left
int idx = left;
if (sorted.get(left) < target) {
idx = left + 1;
}
sorted.add(idx, target);
return idx;
}
}