315. Count of Smaller Numbers After Self
leetcode hard
#array#csharp#hard#leetcode#tree#two-pointers
Task
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример
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.
C# solution
matched/originalpublic class Solution {
public IList<int> CountSmaller(int[] nums) {
int offset = 10000;
int size = 2 * 10000 + 1;
int[] tree = new int[size * 2];
List<int> result = new List<int>();
for (int i = nums.Length - 1; i >= 0; i--) {
int smallerCount = Query(0, nums[i] + offset, tree, size);
result.Add(smallerCount);
Update(nums[i] + offset, 1, tree, size);
}
result.Reverse();
return result;
}
private void Update(int index, int value, int[] tree, int size) {
index += size;
tree[index] += value;
while (index > 1) {
index /= 2;
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}
private int Query(int left, int right, int[] tree, int size) {
int result = 0;
left += size;
right += size;
while (left < right) {
if (left % 2 == 1) {
result += tree[left];
left++;
}
left /= 2;
if (right % 2 == 1) {
right--;
result += tree[right];
}
right /= 2;
}
return result;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int> CountSmaller(vector<int>& nums) {
int offset = 10000;
int size = 2 * 10000 + 1;
vector<int>& tree = new int[size * 2];
List<int> result = new List<int>();
for (int i = nums.size() - 1; i >= 0; i--) {
int smallerCount = Query(0, nums[i] + offset, tree, size);
result.push_back(smallerCount);
Update(nums[i] + offset, 1, tree, size);
}
result.Reverse();
return result;
}
private void Update(int index, int value, vector<int>& tree, int size) {
index += size;
tree[index] += value;
while (index > 1) {
index /= 2;
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}
private int Query(int left, int right, vector<int>& tree, int size) {
int result = 0;
left += size;
right += size;
while (left < right) {
if (left % 2 == 1) {
result += tree[left];
left++;
}
left /= 2;
if (right % 2 == 1) {
right--;
result += tree[right];
}
right /= 2;
}
return result;
}
}Java solution
matched/originalclass Solution {
public List<Integer> countSmaller(int[] nums) {
int offset = 10000;
int size = 2 * 10000 + 1;
int[] tree = new int[size * 2];
List<Integer> result = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i--) {
int smaller_count = query(0, nums[i] + offset, tree, size);
result.add(smaller_count);
update(nums[i] + offset, 1, tree, size);
}
Collections.reverse(result);
return result;
}
private void update(int index, int value, int[] tree, int size) {
index += size;
tree[index] += value;
while (index > 1) {
index /= 2;
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}
private int query(int left, int right, int[] tree, int size) {
int result = 0;
left += size;
right += size;
while (left < right) {
if (left % 2 == 1) {
result += tree[left];
left++;
}
left /= 2;
if (right % 2 == 1) {
right--;
result += tree[right];
}
right /= 2;
}
return result;
}
}JavaScript solution
matched/originalclass Solution {
countSmaller(nums) {
const offset = 10000;
const size = 2 * 10000 + 1;
const tree = new Array(size * 2).fill(0);
const result = [];
for (let i = nums.length - 1; i >= 0; i--) {
const smallerCount = this.query(0, nums[i] + offset, tree, size);
result.push(smallerCount);
this.update(nums[i] + offset, 1, tree, size);
}
return result.reverse();
}
update(index, value, tree, size) {
index += size;
tree[index] += value;
while (index > 1) {
index = Math.floor(index / 2);
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}
query(left, right, tree, size) {
let result = 0;
left += size;
right += size;
while (left < right) {
if (left % 2 === 1) {
result += tree[left];
left++;
}
left = Math.floor(left / 2);
if (right % 2 === 1) {
right--;
result += tree[right];
}
right = Math.floor(right / 2);
}
return result;
}
}Python solution
matched/originalclass Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
def update(index, value, tree, size):
index += size
tree[index] += value
while index > 1:
index //= 2
tree[index] = tree[index * 2] + tree[index * 2 + 1]
def query(left, right, tree, size):
result = 0
left += size
right += size
while left < right:
if left % 2 == 1:
result += tree[left]
left += 1
left //= 2
if right % 2 == 1:
right -= 1
result += tree[right]
right //= 2
return result
offset = 10**4
size = 2 * 10**4 + 1
tree = [0] * (2 * size)
result = []
for num in reversed(nums):
smaller_count = query(0, num + offset, tree, size)
result.append(smaller_count)
update(num + offset, 1, tree, size)
return reversed(result)Go solution
matched/originalpackage main
import (
"fmt"
"sort"
)
func countSmaller(nums []int) []int {
offset := 10000
size := 2 * 10000 + 1
tree := make([]int, size * 2)
result := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
smallerCount := query(0, nums[i] + offset, tree, size)
result[i] = smallerCount
update(nums[i] + offset, 1, tree, size)
}
return result
}
func update(index, value int, tree []int, size int) {
index += size
tree[index] += value
for index > 1 {
index /= 2
tree[index] = tree[index * 2] + tree[index * 2 + 1]
}
}
func query(left, right int, tree []int, size int) int {
result := 0
left += size
right += size
for left < right {
if left % 2 == 1 {
result += tree[left]
left++
}
left /= 2
if right % 2 == 1 {
right--
result += tree[right]
}
right /= 2
}
return result
}
func main() {
nums := []int{5, 2, 6, 1}
fmt.Println(countSmaller(nums))
}Explanation
Algorithm
1️⃣
Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.
2️⃣
Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.
3️⃣
Верните результат.
😎