315. Count of Smaller Numbers After Self
Given an integer array nums, return an integer array counts 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:
Example 3:
Solution:
class Solution {
public List<Integer> countSmaller(int[] nums) {
/*
[ 5 , 2 , 6, 1]
i
*/
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++){
int cur = nums[i];
nums[i] = 0;
for (int j = i + 1; j < nums.length; j++){
if (cur > nums[j]){
nums[i]++;
}
}
}
for (int i = 0; i < nums.length; i++){
result.add(nums[i]);
}
return result;
}
}
// TC: O(n^2)
// SC: O(n)
// TLE
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
int[] counts = new int[nums.length]; // [0, 0, 0, 0]
int[] indices = new int[nums.length];
for (int i = 0; i < nums.length; i++){
indices[i] = i;
}
// indices [0, 1 , 2, 3]
int left = 0;
int right = nums.length - 1;
// 5 2 6 1
//.l r
mergeSort(nums, counts, indices, left, right);
for (int i = 0; i < counts.length; i++){
result.add(counts[i]);
}
return result;
}
/*
5 2 6 1
/ \
5 ,2 6, 1
/\ / \
5 2 6 1
\ / \ /
// indices[1, 0] 2, 5 1 ,6 // indices[1, 0, 4, 3]
\ /
1, 2, 5, 6
// indices[4, 2, 1, 3]
*/
private void mergeSort(int[] nums, int[] counts, int[] indices, int left, int right){
if (left >= right){
return;
}
int mid = left + (right - left)/2;
mergeSort(nums, counts, indices, left, mid);
mergeSort(nums, counts, indices, mid + 1, right);
merge(nums, counts, indices, left, right);
}
// // indices [0, 1 , 2, 3]
/*
5 2 6 1
/ \
5 ,2 6, 1
/\ / \
5 2 6 1
\ / \ /
2, 5 1 ,6
\ /
1, 2, 5, 6
*/
private void merge(int[] nums, int[] counts, int[] indices, int left, int right){
int mid = left + (right - left)/2;// 0 1-0/2 = 0
int leftIndex = left; // 0
int rightIndex = mid + 1; // 1
int rightCount = 0;
int[] sorted = new int[right - left + 1];
int sortedIndex = 0;
while(leftIndex <= mid && rightIndex <= right){
// 0 <= 0 && 1 <=1
if (nums[indices[rightIndex]] < nums[indices[leftIndex]]){
// nums[indices[1]] = nums[1] = 2 < nums[indices[0]] = nums[0] = 5 v
rightCount = rightCount + 1; // we find right part has a number large than left
sorted[sortedIndex] = indices[rightIndex];
// sorted[0] = indices[1] // [1, 0, 0, 0]
sortedIndex++; // 1
rightIndex++; // 1
}else{// left 2 , right = 3 mid = 2
counts[indices[leftIndex]] = counts[indices[leftIndex]] + rightCount;
// counts[indices[2]] = counts[3] = counts[indices[2]] = counts[3] + 0 =counts[3]= 0;
sorted[sortedIndex] = indices[leftIndex];
// sorted[0] = indices[2] = 2 [2,0]
sortedIndex++;
leftIndex++;
}
}
// sorted [1, 0]
while(leftIndex <= mid){ // 0, 0
counts[indices[leftIndex]] = counts[indices[leftIndex]] + rightCount;
// count[indices[0]] = count[0] = 1
sorted[sortedIndex] = indices[leftIndex];
// [1,0]
sortedIndex++; //
leftIndex++;
}
while(rightIndex <= right){
sorted[sortedIndex] = indices[rightIndex];
sortedIndex++;
rightIndex++;
}
for (int i = left; i <= right; i++){
// 0 1
indices[i] = sorted[i-left];
// [0, i] = [0-0] =
// indices[0] = sorted[0 - 0] = sorted[0] =1
// indices[1, 0]
}
}
}
// TC: O(nlogn)
// SC: O(n)
class Solution {
public List<Integer> countSmaller(int[] nums) {
// nums: [5, 2, 6, 1]
int n = nums.length;
int[] counts = new int[n]; // 存储最终的计数结果
int[] indices = new int[n]; // 存储每个元素的索引
// 这个循环初始化 indices 数组, 使其元素的值从0到n-1
for (int i = 0; i < n; i++){
indices[i] = i;
}
// indices: [0, 1, 2, 3]
// 开始对数组进行排序, 并在此过程中计算每个右侧小于它的元素数量
// 这个方法采用分而治之的策略, 通过递归分解数组, 然后在合并过程中进行计数
mergeSort(nums, indices, counts, 0, n - 1);
List<Integer> result = new ArrayList<Integer>();
for (int count : counts){
result.add(count);
}
return result;
}
// nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 0, 3
private void mergeSort(int[] nums, int[] indices, int[] counts, int left, int right){
if (left >= right){
return;
}
int mid = left + (right - left)/2; // 0 + (3 -0)/2 = 1
mergeSort(nums, indices, counts, left, mid); //
// nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 0, 1
/* mid = 0 + (1-0)/2 = 0
nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 0, 0
nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 1,1
*/
mergeSort(nums, indices, counts, mid + 1, right);
// nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 2, 3
/*
mid = 2 + (3-2)/2 = 2 + 0=2
nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 2, 2
nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 3, 3
*/
merge(nums, indices, counts, left, right);
// nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 0, 1
}
// nums: [5,2,6,1], indices: [0, 1, 2, 3], counts: [0, 0, 0, 0], 2, 3
private void merge(int[] nums, int[] indices, int[] counts, int left, int right){
int mid = left + (right - left)/2; // 计算中间点，用于分割数组为左右两部分
// 2+(3-2)/2 = 2 + 1 /2 = 2
int leftIndex = left; // 2
int rightIndex = mid + 1; // 3
// 初始化两个指针，leftIndex指向左半部分的起始位置，rightIndex指向右半部分的起始位置
int rightCount = 0;
// 初始化rightCount变量，用于记录当前右侧已经合并到结果数组中的元素数量，这对于更新计数非常关键
int[] sorted = new int[right - left + 1]; // 3-2+1 = 2 sorted[3, 2]
int sortedIndex = 0;
// 创建一个临时数组sorted用于存放当前范围内排序后的元素，
// sortedIndex用于跟踪当前填充到sorted数组中的位置。
while(leftIndex <= mid && rightIndex <= right){
// 2 <= 2 && 3 <= 3
if (nums[indices[rightIndex]] < nums[indices[leftIndex]]){
// nums[indices[3]] = nums[3] = 1 < nums[indics[2]] = nums[2] = 6
rightCount++; // 1
sorted[sortedIndex] = indices[rightIndex]; // sorted[0] = indices[3]=3
sortedIndex++;// 1
rightIndex++;// 3+1
} else {
counts[indices[leftIndex]] = counts[indices[leftIndex]] + rightCount;
sorted[sortedIndex] = indices[leftIndex];
sortedIndex++;
leftIndex++;
}
}
while(leftIndex <= mid){
// 2 <= 2
counts[indices[leftIndex]] = counts[indices[leftIndex]] + rightCount;
// counts[indices[2]]= counts[2] = 0 + 1;
sorted[sortedIndex] = indices[leftIndex];
// sorted[1] = indices[2] = 2
sortedIndex++;// 3
leftIndex++; // 3
}
while(rightIndex <= right){
sorted[sortedIndex] = indices[rightIndex];
sortedIndex++;
rightIndex++;
}
for (int i = left; i <= right; i++){
indices[i] = sorted[i - left];
}
// 2 <=3
// indices[2] = sorted[2-2] = 3
// 2
}
}
// Time Complexity: O(Nlog(N)).
// Space Complexity: O(N)
Hard!!!!
https://www.youtube.com/watch?v=bX36G_P83W4 看着半年前的视频 陷入了沉思 咋这么牛逼
...
现在不会了!!!
mergeSort的话会涉及到交换的部分, 每次sort 就是count++
indices 记录的是swap前原来的index顺序
然后利用count[] 再将结果返回到原来的index