要素を交換して、辞書編集的に最小の配列を作成します

2948。要素を交換して辞書順に最小の配列を作成

難易度: 中

トピック: 配列、結合検索、ソート

正の 整数の 0 インデックス 配列と正の整数制限が与えられます。

1 回の操作で、任意の 2 つのインデックス i と j を選択し、nums[i] と nums[j] を入れ替えることができます。if |nums[i] - nums[j]| <= 制限。

操作を何回でも実行することで取得できる 辞書編集上最小の配列を返します。

配列 a は、a と b が異なる最初の位置に、配列 a の要素が b の対応する要素よりも小さい場合、辞書編集的に配列 b より小さくなります。たとえば、配列 [2,10,3] は、インデックス 0 と 2

例 1:

• 入力: 数値 = [1,5,3,9,8]、制限 = 2
• 出力: [1,3,5,8,9]
• 説明: 操作を 2 回適用します:
  nums[1] を nums[2] と交換します。配列は [1,3,5,9,8]
  • になります。
  nums[3] を nums[4] と交換します。配列は [1,3,5,8,9]
  • になります。
  これ以上操作を適用しても、辞書編集的に小さい配列を取得することはできません。
  異なる操作を実行しても同じ結果が得られる可能性があることに注意してください。

例 2:

• 入力: 数値 = [1,7,6,18,2,1]、制限 = 3
• 出力: [1,6,7,18,1,2]
• 説明: 操作を 3 回適用します。
  nums[1] を nums[2] と交換します。配列は [1,6,7,18,2,1]
  • になります。
  nums[0] を nums[4] と交換します。配列は [2,6,7,18,1,1]
  • になります。
  nums[0] を nums[5] と交換します。配列は [1,6,7,18,1,2]
  • になります。
  これ以上操作を適用しても、辞書編集的に小さい配列を取得することはできません。

例 3:

• 入力: 数値 = [1,7,28,19,10]、制限 = 3
• 出力: [1,7,28,19,10]
• 説明: [1,7,28,19,10] は、2 つのインデックスに演算を適用できないため、取得できる辞書編集上の最小の配列です。

例 4:

• 入力: 数値 = [1,60,34,84,62,56,39,76,49,38]、制限 = 4
• 出力: [1,56,34,84,60,62,38,76,49,39]

制約:

1 5 1 9 1 9

ヒント:

1. numのすべての要素がノードであり、条件を満たすペアがそれらの間にエッジを持っている仮想グラフを構築します。
すべてのエッジを構築する代わりに、接続されたコンポーネントのみを気にします。 dsu？
2. を使用できますか
sort nums。ここで、連続した要素が同じ接続コンポーネントに属しているかどうかを確認するためのエッジがあるかどうかを考慮する必要があります。したがって、すべての接続されたコンポーネントは、並べ替え後に位置となる要素のリストになります。
3. 0からnums.length -1のnumsの各インデックスについて、接続されたコンポーネントにある現在の最小値に変更し、接続されたコンポーネントからその値を削除できます。
4. 解決策：

問題は、条件の対象となる配列の要素を交換することにより、

辞書学的に最小のアレイを見つけるように求めています。具体的には、それらの間の絶対差（nums [i] - nums [j] |）が与えられた制限以下である場合、2つの要素nums [i]とnums [j]を交換することができます。

キーポイント

辞書編集順序：アレイAは、最初の異なるインデックスでa [i]＆lt; b [i]。

スワッピング条件
1. ：スワップは、スワップされている数値の差が≤slime。の場合にのみ許可されます。
Efficive Grounging
2. ：Disjoint Set Union（dsu）または並べ替え手法を使用することにより、有効なスワップで接続された要素をグループ化できます。
最適な配置
3. ：各グループについて、インデックスと値を並べ替えて最小の順序を達成します。 アプローチ
4. constructグループ
：配列を仮想グラフとして扱い、有効なスワップがエッジを定義します。ソートを使用して、接続グループまたはDSUを識別してインデックスを効率的にグループ化します。

並べ替えグループ：接続されたインデックスの各グループ内で、要素を辞書的順序で再配置します。

出力構造

：ソートされた値をそれぞれの位置に戻します。
計画
抽出（値、インデックス）ペアでペアを使用してソートして、効率的なグループ検出を可能にします。
3. 並べ替えられた値を繰り返して、限界条件に基づいて接続されたインデックスのグループを形成します。 各グループの場合： インデックスと値を独立してソートします。

値を辞書編集順に元の位置に再割り当てします。

修正された配列を返します。

このソリューションをPHP：
2. 2948に実装しましょう。要素を交換して、辞書編集的に最小のアレイを作成します
3. 説明：
4. 抽出と並べ替え（g​​etNumandIndexes）：

• 簡単に参照できるように、値とインデックスをペアに組み合わせます。
• ペアを値で並べ替えると、連結コンポーネントを効率的にグループ化できます。

グループ化ロジック:

• ソートされたペアをスキャンします。連続する値の差が制限値以下の場合は、それらを同じグループに追加します。それ以外の場合は、新しいグループを開始します。

並べ替えと再割り当て:

• 各グループについて:
  • インデックスと値を抽出します。
  • 両方のリストを並べ替えて、最小の値が最小のインデックスに配置されるようにします。
  • 並べ替えられた値を回答配列内のそれぞれの位置に再割り当てします。

結果の構築:

• すべてのグループを処理した後、更新された配列を返します。

チュートリアルの例

例1

入力: 数値 = [1,5,3,9,8]、制限 = 2

1. 抽出と並べ替え:

   • ペア: [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]
   • ソートされたペア: [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]

2. グループ化:

   • グループ 1: [(1, 0)]
   • グループ 2: [(3, 2), (5, 1)]
   • グループ 3: [(8, 4), (9, 3)]

3. グループの並べ替え:

   • グループ 1: 変更なし ([1])
   • グループ 2: 値 = [3, 5]、インデックス = [1, 2] → 結果: [1, 3, 5]
   • グループ 3: 値 = [8, 9]、インデックス = [3, 4] → 結果: [8, 9]

4. 最終結果: [1, 3, 5, 8, 9]

時間計算量

1. ソート: nums 配列のソートには O(n log n) がかかります。
2. グループ化: ソートされた配列の線形走査には O(n) がかかります。
3. グループの並べ替え: 各グループのインデックスと値の並べ替えには、O(k log k) がかかります。kグループのサイズです。すべてのグループを合計すると、O(n log n) となります。

全体の時間計算量: O(n log n)

例の出力

例 2

入力: 数値 = [1,7,6,18,2,1]、制限 = 3

出力: [1,6,7,18,1,2]

例 3

入力: 数値 = [1,7,28,19,10]、制限 = 3

出力: [1,7,28,19,10]

このアプローチは、並べ替えを使用して接続されたコンポーネントを特定し、各コンポーネント内の値を再配置して辞書編集的に最小の配列を実現することで、問題を効率的に処理します。並べ替えとグループ処理を活用することで、O(n log n) の複雑さを持つ最適なソリューションを保証します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が要素を交換して、辞書編集的に最小の配列を作成しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。