nums = [1,5,3,9,8]，limit = 2
• > >輸出：
[1,3,5,8,9]
• >說(shuō)明：
應(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]
  >我們無(wú)法通過(guò)應(yīng)用任何操作來(lái)獲得詞典較小的陣列。
  • 請(qǐng)注意，可以通過(guò)執(zhí)行不同的操作來(lái)獲得相同的結(jié)果。>
  • >
  >示例2：
輸入：

>輸出：

• >說(shuō)明：應(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]
>我們無(wú)法通過(guò)應(yīng)用任何操作來(lái)獲得詞典較小的陣列。
• • >示例3：
  • >輸入：
  nums = [1,7,28,19,10]，limit = 3
  >輸出：
[1,7,28,19,10]

>說(shuō)明： [1,7,28,19,10]是我們可以獲得的詞典最小的陣列，因?yàn)槲覀儫o(wú)法在任意兩個(gè)指數(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)造一個(gè)虛擬圖，其中數(shù)字中的所有元素都是節(jié)點(diǎn)，并且滿足條件之間的對(duì)之間的邊緣具有邊緣。
  而不是構(gòu)造所有邊緣，我們只關(guān)心連接的組件。
  2. 我們可以使用dsu嗎？
  3. >排序數(shù)字?，F(xiàn)在，我們只需要考慮連續(xù)元素是否具有邊緣來(lái)檢查它們是否屬于相同的連接組件。因此，所有連接的組件在排序后成為位置連續(xù)元素的列表。
  >對(duì)于NUM的每個(gè)索引從0到NUMS.LENGENGES -1，我們可以將其更改為我們?cè)谄溥B接組件中具有的當(dāng)前最小值，并從連接的組件中刪除該值。>
  5. 解決方案：

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

  >關(guān)鍵點(diǎn)

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

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

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

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

  獨(dú)立排序索引和值。>

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

• 分組邏輯：

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

  >

  • 示例演練
示例1

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

>提取和排序：

對(duì)：[（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：沒(méi)有更改（[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]
時(shí)間復(fù)雜度

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

o（n log n）

。
1. 分組：線性遍歷通過(guò)排序的數(shù)組o（n）>。
。
2. 排序組：每個(gè)組的分類索引和值o（k log k） ，其中
3. k 是組大小?？偨Y(jié)所有組，這是o（n log n）。 總體時(shí)間復(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]

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

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

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

>

• LinkedIn
• github