c++ - 中位数在列表中的位置

Question

我有一个未排序的数组，我需要中位数的位置。我知道有几种算法可以在 O(n) 中计算给定数组的中位数，但所有这些算法都包括对数组进行某种重新排序，例如中位数的中位数和随机选择。

我对中位数本身不感兴趣，我只对它在数组中的位置感兴趣。

有什么方法可以在 O(n) 中做到这一点？跟踪所有交换将产生巨大的开销，因此我正在寻找另一种解决方案。

Answer 1

假设您有一组数据，您想要找到它的中位数:

double data[MAX_DATA] = ...

创建一个索引数组，并将每个索引初始化到它自己的位置，如下所示:

int index[MAX_DATA];
for (int i = 0 ; i != MAX_DATA ; i++) {
    index[i] = i;
}

现在实现线性中值算法并进行以下更改:

• 当原始算法将data[i]与data[j]进行比较时，替换为data[index[i]]的比较> 到 data[index[j]]
• 当原算法交换data[i]和data[j]时，交换index[i]和index[ j] 代替。

由于 data 的元素始终保留在它们的位置，修改后的算法将生成中位数在未修改数组中的位置，而不是它在一些元素移动到的数组中的位置不同的地方。

在 C++ 中，您可以使用指针而不是索引来实现它，并使用 std::nth_element在指针的容器上，像这样:

vector<int> data = {1, 5, 2, 20, 10, 7, 9, 1000};
vector<const int*> ptr(data.size());
transform(data.begin(), data.end(), ptr.begin(), [](const int& d) {return &d;});
auto mid = next(ptr.begin(), data.size() / 2);
nth_element(ptr.begin(), mid, ptr.end(), [](const int* lhs, const int* rhs) {return *lhs < *rhs;});
ptrdiff_t pos = *mid - &data[0];
cout << pos << endl << data[pos] << endl;

这是一个link to a demo on ideone .