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 1: Input: nums = [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. Example 2: Input: nums = [-1] Output: [0] Example 3: Input: nums = [-1,-1] Output: [0,0]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
- code TLE
class Solution {
public List<Integer> countSmaller(int[] nums) {
TreeMap<Integer, Integer> m = new TreeMap<>();
int n = nums.length;
int[] res = new int[n];
for (int i = n-1; i >= 0; i--){
int count = 0;
for (int k: m.keySet()){
if (k < nums[i]){
count += m.get(k);
}else{
break;
}
}
res[i] = count;
m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
}
return Arrays.stream(res).boxed().collect(Collectors.toList());
}
}
- code #mergeSort
class Solution {
private int[] result;
private int[] index;
private int[] nums;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
this.nums = nums;
result = new int[n];
index = IntStream.range(0, n).toArray();
mergeSort(0, n);
return Arrays.stream(result).boxed().collect(Collectors.toList());
}
private void mergeSort(int left, int right) {
if (right - left <= 1) {
return;
}
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid, right);
merge(left, right, mid);
}
private void merge(int left, int right, int mid) {
// merge [left, mid) and [mid, right)
int i = left; // current index for the left array
int j = mid; // current index for the right array
// use temp to temporarily store sorted array
List<Integer> temp = new ArrayList<Integer>(right - left);
while (i < mid && j < right) {
if (nums[index[i]] <= nums[index[j]]) {
// j - mid numbers jump to the left side of indices[i]
result[index[i]] += j - mid;
temp.add(index[i]);
i++;
} else {
temp.add(index[j]);
j++;
}
}
// when one of the subarrays is empty
while (i < mid) {
// j - mid numbers jump to the left side of indices[i]
result[index[i]] += j - mid;
temp.add(index[i]);
i++;
}
while (j < right) {
temp.add(index[j]);
j++;
}
// restore from temp
for (int k = left; k < right; k++) {
index[k] = temp.get(k - left);
}
}
}