315. Count of Smaller Numbers After Self
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Дан số nguyên mảng nums, return số nguyên mảng counts, где counts[i] - это количество elementов справа от nums[i], которые меньше nums[i].
Ví dụ
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# lời giải
đã khớp/gốcpublic 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcpackage 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))
}Algorithm
1️⃣
Реализуйте Segment tree (segment tree). Поскольку cây инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.
2️⃣
Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте number на num + offset.
Запросите количество elementов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.
3️⃣
return результат.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.