nth_element

2023-12-29 09:31:23

nth_element 是 C++ 标准库中的一个算法,用于对指定范围的元素进行部分排序。这个算法在给定范围内的元素中,将第 n(由迭代器指定)小的元素移动到正确的位置,并保证该元素左侧的所有元素都不大于它,右侧的所有元素都不小于它。font>

template<class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);
  • first:指向范围起始位置的迭代器。
  • nth:指向范围内要定位的元素的迭代器。
  • last:指向范围结束位置的迭代器。

nth_element 的目的是将范围 [first, last) 中的元素重新排列,使得 nth 处的元素为整个范围中第 nth - first 小的元素。注意,这个函数并不保证元素在 nth 处是完全排序的,而是保证 nth 处的元素是整个范围中的第 nth - first 小的元素。

这个函数的时间复杂度为 O(N),其中 N 是 last - first 的距离。它的效率在处理大型数据集时比完全排序要高,因为它只关心排在中间位置的元素。

举例说明:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {9, 7, 5, 1, 3, 8, 2, 6, 4};

    std::cout << "原始数组:";
    for (const auto &num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 nth_element 将第4小的元素移动到正确的位置 即下标为3的元素
    std::nth_element(numbers.begin(), numbers.begin() + 3, numbers.end());

    std::cout << "经过 nth_element 后的数组:";
    for (const auto &num : numbers) {
        std::cout << num << " "; // 1 2 3 4 5 8 7 6 9 
    }
    std::cout << std::endl;

    std::cout << "第4小的元素是:" << numbers[3] << std::endl; // 4

    return 0;
}

这个函数还可以自己指定谓词, 即排序规则, 用来找第n大的元素(逆向思维也可以)

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = { 9, 7, 5, 1, 3, 8, 2, 6, 4 };
    int n = 4;  // 找第4大的元素

    std::cout << "原始数组:";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 nth_element 找第n大的元素
    std::nth_element(numbers.begin(), numbers.begin() + n - 1, numbers.end(), std::greater<int>());
    // 排序后数组
    for (const auto& num : numbers) {
        std::cout << num << " "; // 9 8 7 6 5 4 3 2 1
    }
    std::cout << std::endl;

    std::cout << "第" << n << "大的元素是:" << numbers[n - 1] << std::endl; // 6

    return 0;
}

文章来源:https://blog.csdn.net/f593256/article/details/135282832
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。