Implementation (Part 1)
Урок 5 из 9 курса Сортировка подсчетом — Серия DSA на Coddy.
Мы построим алгоритм сортировки подсчетом, начиная с этапа подсчета.
Задание
ЛегкоПервая фаза сортировки подсчетом (Counting Sort) заключается в подсчете того, как часто встречается каждое значение. Давайте реализуем это.
Напишите функцию с именем countOccurrences, которая принимает массив неотрицательных целых чисел arr (где каждое значение находится в диапазоне от 0 до k - 1) и целое число k, и возвращает массив длиной k, где в позиции v указано, сколько раз число v встречается в arr.
Например, countOccurrences([1, 3, 1, 2, 0], 4) возвращает [1, 2, 1, 1].
Попробуйте сами
#include <stdlib.h>
int* countOccurrences(int* arr, int arr_size, int k, int* returnSize) {
// Напишите код здесь
*returnSize = arr_size;
return arr;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Сортировка подсчетом — Серия DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity