配列のランク変換

1331。配列のランク変換

難易度: 簡単

トピック: 配列、ハッシュ テーブル、ソート

整数 arr の配列が与えられた場合、各要素をそのランクに置き換えます。

ランクは要素の大きさを表します。ランクには次のルールがあります:

• ランクは 1 から始まる整数です。
• 要素が大きいほどランクも大きくなります。 2 つの要素が等しい場合、それらのランクは同じでなければなりません。
• ランクはできるだけ小さくする必要があります。

例 1:

• 入力: arr = [40,10,20,30]
• 出力: [4,1,2,3]
• 説明: 40 が最大の要素です。 10が最小です。 20 は 2 番目に小さいです。 30 は 3 番目に小さいです。

例 2:

• 入力: arr = [100,100,100]
• 出力: [1,1,1]
• 説明: 同じ要素は同じランクを共有します。

例 3:

• 入力: arr = [37,12,28,9,100,56,80,5,12]
• 出力: [5,3,4,2,8,6,7,1,3]

制約:

• 0 5
• -10⁹ 9

ヒント:

1. 一時配列を使用して配列をコピーし、並べ替えます。
2. 各要素のランクは、並べ替えられた配列内のそれよりも小さい一意の要素の数に 1 を加えたものです。

解決策:

次のステップに分けることができます:

1. 配列をコピーして並べ替えます。 これは、各一意の要素のランクを決定するのに役立ちます。
2. ハッシュ マップを使用して要素にランクを割り当てます。 複数の要素が同じ値を共有できるため、ハッシュ マップ (PHP の連想配列) は各要素をそのランクにマッピングするのに役立ちます。
3. 元の要素をそのランクで置き換えます: ハッシュ マップを使用すると、元の配列の各要素を対応するランクで置き換えることができます。

このソリューションを PHP で実装してみましょう: 1331。配列のランク変換

<?php /**
 * @param Integer[] $arr
 * @return Integer[]
 */
function arrayRankTransform($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr1 = [40, 10, 20, 30];
print_r(arrayRankTransform($arr1)); // Output: [4, 1, 2, 3]

$arr2 = [100, 100, 100];
print_r(arrayRankTransform($arr2)); // Output: [1, 1, 1]

$arr3 = [37, 12, 28, 9, 100, 56, 80, 5, 12];
print_r(arrayRankTransform($arr3)); // Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]
?>

説明：

1. 配列をコピーして並べ替えます:

   • 入力配列 $sorted のコピーを作成し、それを並べ替えます。これは、各固有の要素のランクを決定するのに役立ちます。

2. 要素にランクを割り当てる:

   • ソートされた配列を反復処理し、ハッシュ マップ $rank を使用して各一意の要素のランクを保存します。
   • isset を使用して、要素にすでにランクが割り当てられているかどうかを確認します。そうでない場合は、現在のランクを割り当てて増分します。

3. 要素をランクで置き換えます:

   • 次に、元の配列を反復処理し、$rank ハッシュ マップで検索して各要素を対応するランクに置き換えます。

時間計算量:

• 配列のソートには O(n log n) がかかります。n は配列のサイズです。
• ランクの割り当てと値の置換には、O(n) がかかります。
• 全体の時間計算量は O(n log n) です。

このソリューションは、シンプルさを維持しながら大規模な配列を効率的に処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が配列のランク変換の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。