透過交換元素形成字典順序最小的數組

2948。通過交換元素形成字典順序最小的數組

難度：中等

主題：數組、並集查找、排序

您將獲得一個0索引數組，其中包含正個整數nums和一個正整數限制。

在一次操作中，您可以選擇任意兩個索引i 和j 並交換nums[i] 和nums[j] if |nums[i] - nums[j]|

返回按字典順序最小的數組，可以通過執行任意次操作獲得。

如果在 a 和 b 不同的第一個位置，數組 a 的元素小於 b 中對應的元素，則數組 a 按字典順序小於數組 b。例如，數組 [2,10,3] 按字典順序小於數組 [10,2,3]，因為它們在索引 0 和 2

示例1：

• 輸入： nums = [1,5,3,9,8], limit = 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：

• 輸入： nums = [1,7,6,18,2,1], limit = 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：

• 輸入： nums = [1,7,28,19,10], limit = 3
• 輸出： [1,7,28,19,10]
• 解釋： [1,7,28,19,10] 是我們可以獲得的按字典順序排列的最小數組，因為我們無法對任意兩個索引應用該操作。

示例 4：

• 輸入： nums = [1,60,34,84,62,56,39,76,49,38], limit = 4
• 輸出： [1,56,34,84,60,62,38,76,49,39]

約束：

1 5 1 9 1 9

提示：

1. 構造一個虛擬圖，其中數字中的所有元素都是節點，並且滿足條件之間的對之間的邊緣具有邊緣。
而不是構造所有邊緣，我們只關心連接的組件。
2. 我們可以使用dsu嗎？
3. >排序數字。現在，我們只需要考慮連續元素是否具有邊緣來檢查它們是否屬於相同的連接組件。因此，所有連接的組件在排序後成為位置連續元素的列表。
>對於NUM的每個索引從0到NUMS.LENGENGES -1，我們可以將其更改為我們在其連接組件中具有的當前最小值，並從連接的組件中刪除該值。 >
5. 解決方案：

問題要求我們通過交換陣列的元素來找到詞典最小的數組。具體而言，如果它們之間的絕對差異（| nums [i] - nums [j] |）小於或等於給定的極限。

>關鍵點

：一個陣列A在第一個不同的索引，A [i]＆lt; b [i]。

交換條件

：僅在交換數字之間的差異≤LIMIND時才允許交換。
1. >有效分組：通過使用
2. 分離設置聯合（dsu）或排序技術，我們可以分組通過有效換件連接的元素。
3. >最佳佈置：對於每個組，對索引和值進行排序以達到最小的順序。
方法

構建組

：將數組視為虛擬圖，其中有效交換定義邊緣。使用排序以有效地識別連接的組或DSU分組索引。 >

排序組

：在每組連接的索引中，按詞典順序重新排列元素。
1. >輸出構建
：將排序值放回其各自的位置。
2. 計劃
3. 提取（值，索引）對並按值對它們進行排序以啟用有效的組檢測。 通過排序的值迭代，以形成根據極限條件連接的索引組的組。
>

>對於每個組：

獨立排序索引和值。 >

>以詞典順序重新分配其原始位置。

返回修改後的數組。
3. >讓我們在PHP中實現此解決方案： 2948。通過交換元素
   • 使詞典最小的數組製作最小的陣列
   解釋：

>提取和排序（getnumandIndexes）：

• >將值和索引組合為對以易於參考。
>按值將成對排序，以實現有效的連接組件分組。
• >

分組邏輯：

穿越分類對。如果連續值之間的差為≤限制，請將它們加到同一組中；否則，啟動一個新組。

排序與重新分配：

>對於每組：

• 提取索引和值。
  >
  • 對兩個清單進行排序，以確保將最小的值放在最小的索引中。 在答案數組中，將排序的值重新指派給它們各自的位置。
結果建構：

處理所有群組後，返回更新的陣列。

>

• 範例演練

範例1

輸入： nums = [1,5,3,9,8]，limit = 2

>擷取與排序：

對：[（1，0），（5，1），（3，2），（9，3），（8，4）]

1. >排序對：[（1，0），（3，2），（5，1），（8，4），（9，3）]

   • 分組：
組1：[（1，0）]

2. 第2組：[（3，2），（5，1）] 第3組：[（8，4），（9，3）]

   • 排序組：
   組1：沒有更改（[1]）
3. 組2：值= [3，5]，indices = [1，2]→結果：[1，3，5]

   組3：值= [8，9]，indices = [3，4]→結果：[8，9]

   • 最終結果：
   [1，3，5，8，9]
時間複雜度

4. 排序：
排序數位

o（n log n）

。

。
1. 分組：線性遍歷通過排序的陣列o（n）>。
。
2. 排序組：每組的分類索引和值o（k log k） ，其中
3. k 是組別大小。總結所有組別，這是o（n log n）。 整體時間複雜度：

o（n log n）

>輸出範例

範例2

>輸入：

nums = [1,7,6,18,2,1]，limit = 3

>輸出： [1,6,7,18,1,2]

範例3

> input：

nums = [1,7,28,19,10]，limit = 3

>輸出： [1,7,28,19,10]

>這種方法透過使用排序來識別每個組件內的連接組件和重新排列值以實現詞典上最小的數組來有效地處理問題。透過利用排序和群組處理，我們確保使用>o（n log n）

複雜性的最佳解決方案。 聯絡連結

如果您發現此系列有幫助，請考慮在Github上給出 reposority >在您喜歡的社交網絡上分享帖子？您的支持對我來說意義重大！ >

如果您想要這樣的更多有用的內容，請隨時關注我：

>

• LinkedIn
• github

以上是透過交換元素形成字典順序最小的數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！