问题标签 [nth-element]

我很难掌握应该如何使用std::nth_element，因为我有点生疏了。

裁判说：

重新排列 range[first,last)中的元素，使得第 n 个位置的元素是排序序列中该位置的元素。

我想获取向量子集的第 n 个元素，所以我想这样做：

将意味着v从start，直到end（不包括）向量 的子集，然后假设该子集已排序，定位nTh元素。

看来我的理解是错误的，因为这个玩具示例：

打印 9 作为请求的元素，而我期待 5。请问我错过了什么？

我希望从 C++ 中的浮点数组中计算中值：

FloatArray 包含一个常规的 C++ 浮点数组。

我正在使用std::nth_element，但想知道是否有这样的设施nth_element可以处理const数据？现在，我正在制作一个副本，然后nth_element在扔掉之前做。如果没有类似nth_elementfor constdata 的东西，是否有更有效的方法使用复制步骤来计​​算信息，从而避免潜在的额外 O(n) 循环？也许性能影响可以忽略不计？我的数组大小可能在 20 亿左右。

I need an algorithm which can find the median of a singly linked list in linear time complexity O(n) and constant space complexity O(1).

EDIT: The singly linked list is a C-style singly linked list. No stl allowed (no container, no functions, everything stl is forbidden, e.g no std::forward_list). Not allowed to move the numbers in any other container (like an array). It's acceptable to have a space complexity of O(logn) as this will be actually even under 100 for my lists. Also I am not allowed to use the STL functions like the nth_element

Basically I have linked list with like 3 * 10^6 elements and I need to get the median in 3 seconds, so I can't use a sorting algoritm to sort the list (that will be O(nlogn) and will take something like 10-14 seconds maybe).

I've done some search online and I've found that it's posibile to find the median of an std::vector in O(n) and O(1) space compleity with quickselect (the worst case is in O(n^2), but it is rare), example: https://www.geeksforgeeks.org/quickselect-a-simple-iterative-implementation/

But I can't find any algoritm that does this for a linked list. The issue is that I can use the array index to randomly acces the vectorIf I want to modify that algoritm the complexity will be much bigger, because. For example when I change the pivotindex to the left I actually need to traverse the list to get that new element and go further (this will get me at least O(kn) with a big k for my list, even aproching O(n^2)...).

EDIT 2:

I know I have too many variables but I've been testing different stuff and I am still working on my code... My current code:

Do you have any sugestion on how to adapt quickselect to a singly listed link or other algoritm that would work for my problem ?

为了理解quick_sort我正在尝试实现nth_element。
作为测试的基本事实，我正在使用std::nth_element
我的算法在许多输入上都失败了，例如 a = {6,1,7,5,3,8,2,4,9}
如何解决？

如果我在循环中进行测试，则更新算法失败：

正如标题所提到的，我的目标是在犰狳矩阵上使用 std::nth_element，该矩阵包含一组 d 维的 N 点，即 Nxd 矩阵。这些行代表一个 d 维点。两行的比较应该沿着一个固定的维度进行，即

row(i) < row(j) iff A(i, s) < A(j,s) （比较每行的 s 条目）。

我现在的想法是使用 Armadillo 提供的列迭代器并重载 std::swap 函数以与两个列迭代器和我想要的交换一起使用：

这里我使用了 arma::mat 中的 swap_rows 方法。对 std::nth_element 的调用如下所示：

现在的问题是，以上述方式重载交换时出现编译器错误：

我猜这些错误告诉我列迭代器无法访问它所操作的矩阵 M？此外，似乎我无法访问我的迭代器所在的 current_row 。我尝试查看犰狳文档，但除了它的存在以及如何使用begin(). 同样查看犰狳的实际代码对我没有帮助，因为我还没有找到arma:mat::col_iterator.

所以我的问题是上述错误告诉我什么，我该如何解决这个问题？此外，如果您碰巧知道解决所描述问题的更好方法，那也将受到高度赞赏。:)

之前，我尝试为 arma::mat 的行编写自定义随机访问运算符，但这失败了，因为我无法重载value_type& operator*() { return A.row(i); }，因为A.row(i)似乎返回了一个临时的 arma::vec 对象或其他东西。

编辑：我应该提到我尝试使用此代码片段实现我自己的迭代器并根据我的需要进行调整。上面的交换函数也受到此代码片段的启发。

在我接触到算法之前，我几乎已经了解了许多 STL 算法std::nth_element。我被困住了；我不知道它是如何工作的，它确实做到了。

为了教育和理解，有人可以向我解释算法是如何std::nth_element工作的吗？

输出：

• 那么nth元素在哪里呢？
• 该算法如何以及做什么？
• 它是否进行某种部分排序？

以下是来自 cppreference.com 的一些解释：

nth_element是一种部分排序算法，它重新排列 [first, last) 中的元素，使得：

• 如果 [first, last) 已排序，则 nth 指向的元素将更改为该位置将出现的任何元素。
• 这个新的第 n 个元素之前的所有元素都小于或等于新的第 n 个元素之后的元素。更正式地说，nth_element 按升序对范围 [first, last) 进行部分排序，以便范围 [first, nth) 中的任何 i 和范围内的任何 j 都满足条件!(*j < *i)（对于第一个版本或第二个版本）comp(*j, *i) == false范围 [nth, last)。如果范围已完全排序，则放置在第 n 个位置的元素正是在该位置出现的元素。

nth 可能是结束迭代器，在这种情况下该函数无效。

• 我仍然对此感到困惑。什么是第 n 个元素以及如何实现这样的可能算法？为了教育起见，我模仿了许多 STL 算法。太感谢了！