9 4 4 9 2 2 のような並べ替えられていない配列が与えられた場合、その配列が並べ替えられたときに、その配列内の各桁の開始位置と終了位置を知ることができる効率的なアルゴリズムが必要です。たとえば、上記の配列の場合、数字 2 の開始インデックスは 0 で、終了インデックスは 1 です。数字 4 の開始インデックスは 2 で終了インデックスは 3 で、数字 9 の開始インデックスは4 のインデックスと 5 の終了インデックス (ソート時)。これを効率的に行う方法を知っている人はいますか？最初に配列をソートせずにそれを行う方法はありますか?
質問する
131 次
1 に答える
5
異なる要素が 10 個しかないという事実を利用できます。
まず、ゼロ、1、2 などを数えながら、配列を 1 回繰り返します。
これらのカウントから、ソートされた配列内の各桁の開始位置と終了位置を簡単に割り出すことができます。
これはCounting Sortのバリアントですが、並べ替えられた配列に実際にデータを入力しない点が異なります。
于 2013-04-08T18:38:16.377 に答える