c++ - 我怎样才能重新排列数组以更快地获得最小值、中值和最大值？

Question

我想重复重新排列一个数组或std::vector，使最小值是第一个元素，最大值是最后一个元素，arr [(0+lastIdx)/2] 将是中位数，中位数之前的元素小于中位数，中位数之后的元素将更大。每次查询最小值、最大值和中值后，我都会对数据进行更改，我想再次快速查询这三个值。

每次我想重新排列数组时，数组都是具有相同大小的不同数组。

使用 std::nth_element 我可以在正确的位置获得中位数，然后我可以迭代数组以获得最小值和最大值。对于单个数组，这达到了 O(n) 复杂度，显然这无法改进。 (也许除了 O(n) 前面的复杂度常数)

我需要对一个数组进行操作，首先，我重新排列数组，然后做其他事情，这会使排列的数组再次完全没有排列，但没有插入新值。然后，我一遍又一遍地重复这个过程。

Answer 1

即使您以某种方式设法将定位最小值、最大值、中值的成本降低到零， 您仍然需要将错位的元素放在中位数以下或以上。这意味着最坏的情况 n/2 - 1 permutations每一次。

1. 第一遍，找到最小值及其位置(O(n) 时间，O(1) 空间)
2. 第二遍，找到最大值及其位置(O(n) 时间，O(1) 空间)
3. 第三遍，find the median及其位置使用 median of median algorithm (O(n) 时间，O(1) 空间)
4. 通过交换将最小值、最大值、中值放在各自的位置(0、n-1、n/2)
5. 现在您有两个索引:一个从 0 开始用于下方, 和上面的一个开始于 n-1 .而当前below元素在它应该在的位置，增加该索引。虽然当前 above元素在它应该在的位置，减少该索引。当发现放错位置的元素时，上下交换。重复只要below < above . (O(n) 时间，O(1) 空间)

第 4、5 步的逻辑:当它们应该高于时低于中值的元素的数量正好是高于和应该低于的元素的数量。

当然，您可以在一个函数中合并传递 1、2、3，但这不会影响复杂性

让我们运行:

{3, 7, 9, 6, 8, 1, 4, 5, 2}

传递 1、2、3:min_pos = 5, max_pos = 2, median_pos = 7, median = 5

swap (0, min_pos)    -> {1, 7, 9, 6, 8, 3, 4, 5, 2}
swap (9, max_pos)    -> {1, 7, 2, 6, 8, 3, 4, 5, 9}
swap (4, median_pos) -> {1, 7, 2, 6, 5, 3, 4, 8, 9}

现在below_pos = 0 above_pos = 8 .元素没有错位。 下面的下一个错位是位置 1 的 7。下一个错位的上面是位置 6 的 4。

swap (1, 6) -> {1, 4, 2, 6, 5, 3, 7, 8, 9}

下面的下一个错位是位置 3 的 6。下一个错位的是位置 5 的 3。

swap (3, 5) -> {1, 4, 2, 3, 5, 6, 7, 8, 9}

算法输出

{1, 4, 2, 3, 5, 6, 7, 8, 9}