配列のランク変換

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⁹ <= arr[i] <= 10⁹

ヒント:

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

解決策:

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

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

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

  
  
  説明：




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


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



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


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



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


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





  
  
  時間計算量:



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


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

連絡先リンク

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

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


LinkedIn
GitHub



          

            
  

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