План курса / Все задачи / Алгоритмы и структуры данных
Статистика возрастов
сложно
# решено
Дан массив ages, где 0 ≤ ages[i] ≤ 140, и список запросов stats, каждый из которых представляет собой диапазон [x, y], где x ≤ y. Для каждого запроса определите, сколько людей имеют возраст, попадающий в этот диапазон (включительно).
public class Solution {
public static List<int> BuildReport(List<int> ages, List<List<int>> stats) {
// Подсчитываем количество людей по каждому возрасту
int[] freq = new int[141];
foreach (int age in ages) {
freq[age]++;
}
// Строим префиксную сумму по возрастам
int[] px = new int[142];
int count = 0;
for (int i = 1; i <= 141; i++) {
count += freq[i - 1];
px[i] = count;
}
List<int> result = new List<int>(stats.Count);
// Обрабатываем каждый запрос
foreach (var request in stats) {
// За O(1) узнаем число людей в диапазоне
int rawFrom = request[0];
int rawTo = request[1];
// Если диапазон полностью вне допустимого интервала — ответ 0
if (rawTo < 0 || rawFrom > 140) {
result.Add(0);
continue;
}
// Ограничиваем границы диапазоном [0, 140]
int from = Math.Max(0, rawFrom);
int to = Math.Min(140, rawTo);
// Количество людей в диапазоне [from, to]
result.Add(px[to + 1] - px[from]);
}
return result;
}
}
#include <vector>
using namespace std;
vector<int> buildReport(vector<int> &ages, vector<vector<int>> &stats) {
// Подсчитываем количество людей по каждому возрасту
int freq[141] = {0};
for (int age : ages) {
freq[age]++;
}
// Строим префиксную сумму по возрастам
int px[142] = {0};
int count = 0;
for (int i = 1; i <= 141; i++) {
count += freq[i - 1];
px[i] = count;
}
vector<int> result;
result.reserve(stats.size());
// Обрабатываем каждый запрос
for (vector<int> &request : stats) {
// За O(1) узнаем число людей в диапазоне
int rawFrom = request[0];
int rawTo = request[1];
// Если диапазон полностью вне допустимого интервала — ответ 0
if (rawTo < 0 || rawFrom > 140) {
result.push_back(0);
continue;
}
// Ограничиваем границы диапазоном [0, 140]
int from = max(0, rawFrom);
int to = min(140, rawTo);
// Количество людей в диапазоне [from, to]
result.push_back(px[to + 1] - px[from]);
}
return result;
}
package main
func buildReport(ages []int, stats [][]int) []int {
// Подсчитываем количество людей по каждому возрасту
freq := make([]int, 141)
for _, age := range ages {
freq[age]++
}
// Строим префиксную сумму по возрастам
px := make([]int, 142)
count := 0
for i := 1; i <= 141; i++ {
count += freq[i-1]
px[i] = count
}
result := make([]int, 0, len(stats))
// Обрабатываем каждый запрос
for _, request := range stats {
// За O(1) узнаем число людей в диапазоне
rawFrom := request[0]
rawTo := request[1]
// Если диапазон полностью вне допустимого интервала — ответ 0
if rawTo < 0 || rawFrom > 140 {
result = append(result, 0)
continue
}
// Ограничиваем границы диапазоном [0, 140]
from := max(0, rawFrom)
to := min(140, rawTo)
// Количество людей в диапазоне [from, to]
result = append(result, px[to+1]-px[from])
}
return result
}
import java.util.*;
public class Solution {
public List<Integer> buildReport(List<Integer> ages, List<List<Integer>> stats) {
// Подсчитываем количество людей по каждому возрасту
int[] freq = new int[141];
for (int age : ages) {
freq[age]++;
}
// Строим префиксную сумму по возрастам
int[] px = new int[142];
int count = 0;
for (int i = 1; i <= 141; i++) {
count += freq[i - 1];
px[i] = count;
}
List<Integer> result = new ArrayList<>(stats.size());
// Обрабатываем каждый запрос
for (List<Integer> request : stats) {
// За O(1) узнаем число людей в диапазоне
int rawFrom = request.get(0);
int rawTo = request.get(1);
// Если диапазон полностью вне допустимого интервала — ответ 0
if (rawTo < 0 || rawFrom > 140) {
result.add(0);
continue;
}
// Ограничиваем границы диапазоном [0, 140]
int from = Math.max(0, rawFrom);
int to = Math.min(140, rawTo);
// Количество людей в диапазоне [from, to]
result.add(px[to + 1] - px[from]);
}
return result;
}
}
from typing import *
def build_report(ages: List[int], stats: List[List[int]]) -> List[int]:
# Подсчитываем количество людей по каждому возрасту
freq = [0] * 141
for age in ages:
freq[age] += 1
# Строим префиксную сумму по возрастам
px = [0] * 142
count = 0
for i in range(1, 142):
count += freq[i - 1]
px[i] = count
result = []
# Обрабатываем каждый запрос
for request in stats:
# За O(1) узнаем число людей в диапазоне
raw_from = request[0]
raw_to = request[1]
# Если диапазон полностью вне допустимого интервала — ответ 0
if raw_to < 0 or raw_from > 140:
result.append(0)
continue
# Ограничиваем границы диапазоном [0, 140]
from_ = max(0, raw_from)
to = min(140, raw_to)
# Количество людей в диапазоне [from, to]
result.append(px[to + 1] - px[from_])
return result
/**
* @param {number[]} ages
* @param {number[][]} stats
* @returns {number[]}
*/
export function buildReport(ages, stats) {
// Подсчитываем количество людей по каждому возрасту
const freq = new Array(141).fill(0);
for (const age of ages) {
freq[age]++;
}
// Строим префиксную сумму по возрастам
const px = new Array(142).fill(0);
let count = 0;
for (let i = 1; i <= 141; i++) {
count += freq[i - 1];
px[i] = count;
}
const result = [];
// Обрабатываем каждый запрос
for (const request of stats) {
// За O(1) узнаем число людей в диапазоне
const rawFrom = request[0];
const rawTo = request[1];
// Если диапазон полностью вне допустимого интервала — ответ 0
if (rawTo < 0 || rawFrom > 140) {
result.push(0);
continue;
}
// Ограничиваем границы диапазоном [0, 140]
const from = Math.max(0, rawFrom);
const to = Math.min(140, rawTo);
// Количество людей в диапазоне [from, to]
result.push(px[to + 1] - px[from]);
}
return result;
}
Оценка сложности
Время: O(n + m), где n - размер ages, m - размер stats