Implementation (Part 1)
Coddyの「カウンティングソート - DSAシリーズ」コースのレッスン 5/9。
カウンティングソートを、そのカウントフェーズから順に構築していきます。
チャレンジ
簡単カウンティングソートの第一段階は、各値が何回出現するかを集計することです。それを構築してみましょう。
非負整数の配列 arr（すべての値は 0 から k - 1 の間）と整数 k を受け取り、位置 v に v が arr 内に出現する回数を保持する長さ k の配列を返す、countOccurrences という名前の関数を作成してください。
例えば、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