问题标签 [nth-element]

我最近发现在 STL中有一个名为nth_element的方法。引用描述：

Nth_element 类似于 partial_sort，因为它对一系列元素进行部分排序：它排列范围 [first, last) 使得迭代器 nth 指向的元素与如果整个元素位于该位置的元素相同range [first, last) 已排序。此外，范围 [nth, last) 中的任何元素都不小于范围 [first, nth) 中的任何元素。

它声称平均具有 O(n) 复杂度。算法是如何工作的？我找不到任何解释。

我正在将一些 C++ 代码移植到 C#。

C# 是否有等价物std::nth_element()或者我需要自己推出？

我正在尝试编译一个 Octave .oct 函数来计算排序向量的上下“一半”的中位数，该中位数的长度会有所不同，例如对于奇数长度的向量，例如 [5,8,4,6,7]我想要 4,5 和 6 的“下”中值和 6,7 和 8 的“上”中值（6 是两个计算的一部分），以及一个偶数长度向量，例如 [5,8,4 ,6,7,9] 我想要 4,5 和 6 的“下”中值和 7,8 和 9 的“上”中值。我也在尝试使用一种快速的方法来做到这一点并想要使用我已经改编并用于直接中位数计算的代码：-

我可以将输入向量“拆分”成理论上的两半

我遇到的问题是我不确定将上述*注释中位数计算应用于输入向量的指定相关部分的语法。我也许应该提一下，输入是一个 Octave ColumnVector input = args(0).column_vector_value() 并且长度在 10 到 50 个值之间。

有谁知道不同实现的预期运行时间和最坏情况下的运行时间std::nth_element？我几乎每天都使用这个算法。

我对最近的 Microsoft 编译器附带的 STL 版本特别感兴趣，但有关此主题的任何信息都是有帮助的。

请注意，这不是这个问题的重复。我了解存在哪些算法，但我对哪些实现使用哪些算法感兴趣。

作为背景，有众所周知的算法可以做到这一点。一种是 O(n) 平均情况和 O(n log n) 最坏情况，一种是 O(n) 最坏情况但在实践中很慢（中位数的中位数）。另请注意，有一些有趣的实现策略可以在实践中快速获得最坏情况的 O(n) 运行时间。标准说这必须是更糟糕的 O(n) 平均时间。

我编写了一个程序，用户可以在其中输入任意数量的值到向量中，它应该返回四分位数，但我不断收到“向量下标超出范围”错误：

我正在尝试使用 nth_element 找到 (x,y) 点向量的中位数

tempOffsetsX 工作得很好，但有时 tempOffsetsY 在 nth_element 之后会给出非常奇怪的结果。这是标记的调试行的示例输出

在我重新编译之前，结果是相当可重复的，此时细节发生了变化，但一般问题仍然存在。显然，向量以某种方式被破坏了，但我想不出如何。

此外，如果我使用 sort 而不是 nth_element 它可以正常工作。对于调试，我尝试进行排序，然后 nth_element 工作得很好。所以不知何故，在 nth_element 内部发生的重新排序变得一团糟，但我想不出如何。

任何想法这是如何发生的？

编辑- 有关我的环境的更多信息。我正在运行 Arch Linux。我刚刚更新了系统。我应该注意到，相同的代码在更新之前确实可以正常工作，这是我在更新后第一次运行它。但那是几天的差距，我总是不愿指出系统库通常是我自己的问题。

我有一个长度为 n 的数组 A。让 B 是一个包含 A 的每个第 k 个元素的数组（我们永远不想单独存储 - 这只是为了帮助解释）。我想找到 B 的中位数，我想将 A 的那个元素移动到floor(n/2)' 在 A 中的位置。

我怎样才能有效地做到这一点？我正在考虑尝试对 std::nth_element 进行一次调用，将指针传递给 A。但是，我需要这个指针以 A 的 k 个元素递增。我该怎么做？本质上：

其中 kFloat 将是一个类似于浮点数的结构，但是当您增加指针时，它会在内存中移动 k*sizeof(float) 。

注意：我不需要真正的中位数（当 n 为偶数时，中间两个的平均值）。

编辑：另一种表达我想要的方式（不编译，因为 k 不是常数）：

编辑 2：我正在更改 algorithm.cc，所以我不想引入对像 Boost 这样的库的依赖。我只想使用核心 C++11 功能 + std。

我非常接近完成这个程序。它将找到一个包含 5 个值的数组的中位数。我有最后一个错误，我似乎无法摆脱。由于我是 C++ 新手，所以我不知道问题可能是什么。我在这里和谷歌上一遍又一遍地研究错误；没运气。

这是代码：

错误状态：“IntelliSense：没有重载函数“std::nth_element”的实例与参数列表匹配，参数类型为：(std::_Array_iterator, std::_Array_iterator, unsigned int, std::_Array_iterator)

帮我完成这件事！提前致谢。

我正在尝试在 Access 数据库中选择特定值。所以数据库包含很多列，我只能选择第一个值，或者最后一个：

现在我想弄清楚的是如何获得这些列中的第 n 个值。如果 SQL 能够识别第三列（Column7），那将是完美的……我尝试了以下方法：

但这并没有让我到达那里。来自不同列的值不再对应。猜猜我怎么能得到这个？谢谢

我正在尝试在 Access 数据库中选择特定值。所以数据库包含很多列，我只能选择第一个值，或者最后一个：

现在我想弄清楚的是如何获得这些列中的第 n 个值。如果 SQL 能够识别第三列（Column7），那将是完美的……我尝试了以下方法：

但这并没有让我到达那里。来自不同列的值不再对应。

基本上，更具体地说，我实际上并没有尝试列中的第 n 个单元格。它更多的是关于获取特定列中包含的第 n 个值。例如，取下表

因此，我想为每个 column1id 从第 2 列中选择第 n 个值，以便获取第一个元素：

对于第二个元素：

对于第四个：

希望这是有道理的。猜猜我怎么能得到这个？谢谢