3

如果我们有一个整数数组，那么如果每一步唯一允许的操作是：将元素移动到任一极端，我们如何确定对它们进行排序所需的最小步骤（按升序排列）？例如，如果我们有

7 8 9 11 1 10

然后在第一步中可以将 11 移动到右端，在第二步中将 1 移动到左端以获得 1 7 8 9 10 11 。因此总步骤 =2 可以在这里应用冒泡排序吗？但最坏的情况复杂度将是 O(n^2) 。那么我们怎样才能更有效率呢？谢谢。

4

4 回答 4

2

这是一个需要 O(n log n) 时间、O(n) 辅助空间和恰好 n 个 MoveToFront 操作的解决方案。

给定输入数组 A，使用值/索引对创建第二个数组 B，如下所示...

7 8 9 11 1 10  ->  (7 0) (8 1) (9 2) (11 3) (1 4) (10 5)
[this step takes O(n) time and O(n) space]

然后按每对值的降序对 B 进行排序...

(7 0) (8 1) (9 2) (11 3) (1 4) (10 5) -> (11 3) (10 5) (9 2) (8 1) (7 0) (1 4)
[this step takes O(n log n) time]

准备一棵二叉搜索树，T。

现在对 B 中的每个元素执行以下操作...

Let I be the index of this element.
Let V be the sum of I and the number of elements in T that are greater than I.
Do a MoveToFront operation on the Vth element of A.
Add I to T.
[Both of the operations on T take O(log n) time]

这是适用于您的示例数组的算法

(11 3)
    I := 3
    V := 3 + 0 = 3
    MoveToFront(3): 7 8 9 11 1 10  ->  11 7 8 9 1 10
    T: ()  ->  (3)

(10 5)
    I := 5
    V := 5 + 0 = 5
    MoveToFront(5): 11 7 8 9 1 10  ->  10 11 7 8 9 1
    T: (3)  ->  (3 5)

(9 2)
    I := 2
    V := 2 + 2 = 4
    MoveToFront(4): 10 11 7 8 9 1  ->  9 10 11 7 8 1
    T: (3 5)  ->  (2 3 5)

(8 1)
    I := 1
    V := 1 + 3 = 4
    MoveToFront(4): 9 10 11 7 8 1  ->  8 9 10 11 7 1
    T: (2 3 5)  ->  (1 2 3 5)

(7 0)
    I := 0
    V := 0 + 4 = 4
    MoveToFront(4): 8 9 10 11 7 1  ->  7 8 9 10 11 1
    T: (1 2 3 5)  ->  (0 1 2 3 5)

(1 4)
    I := 4
    V := 4 + 1 = 5
    MoveToFront(5): 7 8 9 10 11 1  ->  1 7 8 9 10 11
    T: (0 1 2 3 5)  ->  (0 1 2 3 4 5)

我想您可以找到对使用少于 n 个 MoveToFront/Back 操作的数组进行排序的方法，但我认为您无法在少于 O(n log n) 的时间内找到这些数组。但是，如果这些操作很慢，那么可能值得使用一种需要更多时间来计划的算法，这样您就可以减少这些操作。

于 2012-04-10T07:00:40.200 回答
0

你能稍微澄清一下这个问题吗？当您说列表时，您是指链表还是数组？如果它不是链表，我对有限的操作集有点困惑。如果它是一个链表，您可能可以修改以平均 O(nlgn) 时间运行的快速排序。

于 2012-04-10T03:49:19.967 回答
0

本质上，您提到的数据结构是链表。对于链表，您可以使用快速排序或合并排序（ O(nlogn) ）。

于 2012-04-10T03:50:28.653 回答
0

这听起来不像是排序问题。你只需要找出你需要做多少动作，但你不需要对数组进行排序。我敢打赌，这可以比 O(n log n) 更快地完成

我提出这样的解决方案：只计算有多少 a[i] > a[i - 1]。这将是你的结果。

论证：如果您有 a[i] > a[i-1]，则意味着 a[i] 或 a[i-1] 不在它们的位置。这样你就可以：

1) 将 a[i-1] 移动到数组的开头

2) 将 a[i] 移动到数组的末尾。

更新。您需要定义要移动的 a[i] 或 a[i-1] ，对于数组的示例： 7 8 9 11 1 10 您有两个比较，显示了哪些不合适： 11 > 1 和 11 > 10。所以这绝对是动态规划的任务。但是，它仍然比 O(n log n) 快

于 2012-04-10T07:29:24.493 回答