如何减少数组中的移动操作次数?

问题描述 投票:0回答:1

说我有一组数字,例如[0, 1, 2, 3, 4, 5]和我想结束一个数组,例如[2, 1, 4, 0, 5, 3]。在我看来,我有一个方法可供我使用:

move(fromIndex, toIndex)

因此,为了实现我想要的数组,我可以多次调用该方法:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

因此,我还有一个move()操作列表,以实现我想要的结果。通过更改顺序和索引可以缩小move()操作列表的大小,最终得到相同的结果。

是否有一种算法可以在我的move()操作列表中使用,以将操作次数减少到最少?

arrays algorithm sorting
1个回答
0
投票

我们可以创建一个图形,其元素指向需要交换的数字以到达所需位置。因此,我们将获得具有可能周期的多个图。在您的特定情况下,我们会得到

2-> 0-> 3-> 5-> 4-> 2(第一个和最后一个元素表示一个循环)

这意味着2想要与0交换以到达所需位置。类似地,0想要与3交换以到达所需位置。请注意,1不希望被交换。

现在,我们可以交换图形的两个相邻元素,将图形大小减小1.假设我们交换3和5,所以现在arr = [0,1,2,5,4,3]。现在3处于所需状态,因此我们可以从图中删除它

2->0->5->4->2

我们需要重复此过程(m-1)次以完全删除图形。这里m表示图的边数。我们可以有多个断开的图形或图形,没有周期。我们需要确保我们正在交换同一图表中的元素。最终答案是图表的所有步骤(每个组件的m-1)的总和。

© www.soinside.com 2019 - 2024. All rights reserved.