通过交换元素制作词典最小的阵列

> 2948。通过交换元素

使词典最小的数组制作最小的数组

难度：中等

>主题：数组，联合查找，排序

正整数num和正整数限制的数组。

在一个操作中，您可以选择任何两个索引i和j和交换nums [i]和nums [j]

if | nums [i] - nums [j] | ＆lt; = limit。

返回

词典最小的数组可以通过执行操作多次。

>

>示例1：

输入：

nums = [1,5,3,9,8]，limit = 2
• > >输出：
[1,3,5,8,9]
• >说明：
应用操作2次：
• 用数字[2]交换nums [1]。阵列变为[1,3,5,9,8] 用数字[4]交换nums [3]。阵列变为[1,3,5,8,9]
  >我们无法通过应用任何操作来获得词典较小的阵列。
  • 请注意，可以通过执行不同的操作来获得相同的结果。>
  • >
  >示例2：
输入：

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

>输出：

[1,6,7,18,1,2]

• >说明：应用3次操作：
用数字[2]交换nums [1]。阵列变为[1,6,7,18,2,1]
• 用数字[4]交换nums [0]。阵列变为[2,6,7,18,1,1] 用数字[5]交换nums [0]。阵列变为[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,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. 构造一个虚拟图，其中数字中的所有元素都是节点，并且满足条件之间的对之间的边缘具有边缘。
  而不是构造所有边缘，我们只关心连接的组件。
  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中文网其他相关文章！