nums = [1,5,3,9,8]，limit = 2
• > >輸出：
[1,3,5,8,9]
• >說明：
應(yīng)用操作2次：
• 用數(shù)字[2]交換nums [1]。陣列變?yōu)閇1,3,5,9,8] 用數(shù)字[4]交換nums [3]。陣列變?yōu)閇1,3,5,8,9]
  >我們無法通過應(yīng)用任何操作來獲得詞典較小的陣列。
  • 請注意，可以通過執(zhí)行不同的操作來獲得相同的結(jié)果。>
  • >
  >示例2：
輸入：

>輸出：

• >說明：應(yīng)用3次操作：
用數(shù)字[2]交換nums [1]。陣列變?yōu)閇1,6,7,18,2,1]
• 用數(shù)字[4]交換nums [0]。陣列變?yōu)閇2,6,7,18,1,1] 用數(shù)字[5]交換nums [0]。陣列變?yōu)閇1,6,7,18,1,2]
>我們無法通過應(yīng)用任何操作來獲得詞典較小的陣列。
• • >示例3：
  • >輸入：
  nums = [1,7,28,19,10]，limit = 3
  >輸出：
[1,7,28,19,10]

>說明： [1,7,28,19,10]是我們可以獲得的詞典最小的陣列，因為我們無法在任意兩個指數(shù)上應(yīng)用該操作。

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

>約束：>

1＆lt; = nums.length＆lt; = 10 5 1＆lt; = nums [i]＆lt; = 10 9 > 1＆lt; = limit＆lt; = 10 9

>

提示：
• 1. 構(gòu)造一個虛擬圖，其中數(shù)字中的所有元素都是節(jié)點，并且滿足條件之間的對之間的邊緣具有邊緣。
  而不是構(gòu)造所有邊緣，我們只關(guān)心連接的組件。
  2. 我們可以使用dsu嗎？
  3. >排序數(shù)字?，F(xiàn)在，我們只需要考慮連續(xù)元素是否具有邊緣來檢查它們是否屬于相同的連接組件。因此，所有連接的組件在排序后成為位置連續(xù)元素的列表。
  >對于NUM的每個索引從0到NUMS.LENGENGES -1，我們可以將其更改為我們在其連接組件中具有的當(dāng)前最小值，并從連接的組件中刪除該值。>
  5. 解決方案：

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

  >關(guān)鍵點

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

  交換條件
  ：僅在交換數(shù)字之間的差異≤LIMIND時才允許交換。
  1. >有效分組：通過使用
  2. 分離設(shè)置聯(lián)合（dsu）或排序技術(shù)，我們可以分組通過有效換件連接的元素。
  3. >最佳布置：對于每個組，對索引和值進(jìn)行排序以達(dá)到最小的順序。
  方法
  構(gòu)建組

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

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

  獨立排序索引和值。>

  >以詞典順序重新分配其原始位置。
  返回修改后的數(shù)組。
  3. >讓我們在PHP中實現(xiàn)此解決方案： 2948。通過交換元素
     • 使詞典最小的數(shù)組制作最小的陣列
     解釋：
  >提取和排序（getnumandIndexes）：
  • >將值和索引組合為對以易于參考。
  >按值對成對進(jìn)行排序，以實現(xiàn)有效的連接組件分組。
  • >

• 分組邏輯：

  穿越分類對。如果連續(xù)值之間的差為≤限制，請將它們添加到同一組中；否則，啟動一個新組。
• 排序和重新分配：
  >對于每個組：
  • 提取索引和值。
    >
    • 對兩個列表進(jìn)行排序，以確保將最小的值放在最小的索引中。 在答案數(shù)組中，將排序的值重新分配給它們各自的位置。
  結(jié)果構(gòu)造：
• 處理所有組后，返回更新的數(shù)組。

  >

  • 示例演練
示例1

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

>提取和排序：

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

1. >排序?qū)Γ篬（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]→結(jié)果：[1，3，5]

   組3：值= [8，9]，indices = [3，4]→結(jié)果：[8，9]

   • 最終結(jié)果：
   [1，3，5，8，9]
時間復(fù)雜度

4. 排序：
對數(shù)字陣列進(jìn)行排序

o（n log n）

。
1. 分組：線性遍歷通過排序的數(shù)組o（n）>。
。
2. 排序組：每個組的分類索引和值o（k log k） ，其中
3. k 是組大小。總結(jié)所有組，這是o（n log n）。 總體時間復(fù)雜度：

>輸出示例

示例2

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

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

示例3

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

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

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

復(fù)雜性的最佳解決方案。 聯(lián)系鏈接

如果您發(fā)現(xiàn)此系列有幫助，請考慮在Github上給出 reposority >在您喜歡的社交網(wǎng)絡(luò)上分享帖子？您的支持對我來說意義重大！>

>

• LinkedIn
• github