C ++中的std :: nth_element()

C ++的标准库具有大量功能,虽然并没有那么探讨,但是在特定用法的情况下非常方便。它可以帮助您编写更少的代码并快速执行操作。假设您正在用C ++构建一些后端系统,并且已经有数千行。在这种情况下,这些标准库函数可以极大地减少代码库的大小。同样,在提交时间很重要的竞争性编码中,这些功能的使用可能会让您度过难关!

nth_element()是一个这样的std函数,如果对列表进行了排序,则它有助于在列表范围之外找到第n个元素。

例如,

Say the list is:
[4, 1, 2, 3, 6, 7, 5]

如果您想在整个范围之外找到第三个元素(索引为0),请使用nth_element()函数,将您的列表更新为类似的内容,

[3, 1, 2, 4, 6, 7, 5]

告诉您排序列表中的第三个元素将是arr [3] = 4

此功能的最重要功能是:

  1. 它只会以正确的顺序给出您的第n个元素

  2. 对于元素的其余部分,您无法猜测会是什么安排。这取决于编译器。您可以放心,第n个元素之前的元素都小于第n个元素,而第n个元素之后的元素大于第n个元素。

第n个元素的语法:

void nth_element(iterator start, iterator nth, iterator end)
//所以它不会返回任何东西,
//而是在内部更新列表

iterator start  = start of your range
iterator end    = end of your range
iterator nth    = nth term you want to see in position 
                  if the list was sorted (0-indexed)

因此,对于上面的示例,向量名称为arr。然后,将是:

nth_iterator(arr.begin(),arr+3,arr.end())

由于范围是列表的第一个到最后一个,如果列表已排序,我们需要找到第三个元素(索引为0)。

示例

#include <bits/stdc++.h>
using namespace std;

//打印矢量
void print(vector<int> arr)
{
    for (auto it : arr) {
        cout << it << " ";
    }
    cout << endl;
}

int main(){
    //看看它是如何初始化的 
    vector<int> arr{ 4, 1, 2, 3, 6, 7, 5 };

    cout << "Printing initially...\n";
    print(arr);

    //如果列表已排序,则查找第三个元素
    nth_element(arr.begin(), arr.begin() + 3, arr.end());
    
    cout << "t//如果列表已排序,则第三个元素为: " << arr[3] << endl;

    cout << "the new rearrangement of the array...\n";
    print(arr);
    
    return 0;
}

输出:

Printing initially...
4 1 2 3 6 7 5
t//如果列表已排序,则第三个元素为: 4
the new rearrangement of the array...
3 1 2 4 5 6 7

应用或用途:

如果数组是一次性排序的,则每当需要查找nth_element()时,便可以使用此标准库函数。

一个重要的应用可能是在未排序的数组中找到中值。