杂项算法

当标准库算法的契约符合任务时，应优先使用它们，因为其实现针对目标平台进行了优化。

左侧最近的更小元素 #

在栈中维护递增值。每个索引各入栈和出栈一次，因此时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

cpp

#include <cstddef>
#include <vector>

std::vector<int> nearest_left_smaller(const std::vector<int>& values) {
    std::vector<int> result(values.size(), -1);
    std::vector<std::size_t> stack;
    stack.reserve(values.size());

    for (std::size_t index = 0; index < values.size(); ++index) {
        while (!stack.empty() && values[stack.back()] >= values[index]) {
            stack.pop_back();
        }
        if (!stack.empty()) {
            result[index] = static_cast<int>(stack.back());
        }
        stack.push_back(index);
    }
    return result;
}

当前驱相等也有效时，使用 > 而不是 >=。 Reversing the scan or comparison produces next-greater, stock-span, histogram, and temperature-query variants.

并查集 #

按大小合并和路径折半使 find 和 unite 的摊销复杂度达到 \(O(\alpha(n))\)。 A negative entry stores the root’s component size.

cpp

#include <utility>
#include <vector>

class DisjointSet {
public:
    explicit DisjointSet(int count) : parent_or_size_(count, -1) {}

    int find(int value) {
        while (parent_or_size_[value] >= 0) {
            const int parent = parent_or_size_[value];
            if (parent_or_size_[parent] >= 0) {
                parent_or_size_[value] = parent_or_size_[parent];
            }
            value = parent;
        }
        return value;
    }

    bool unite(int left, int right) {
        left = find(left);
        right = find(right);
        if (left == right) {
            return false;
        }
        if (parent_or_size_[left] > parent_or_size_[right]) {
            std::swap(left, right);
        }
        parent_or_size_[left] += parent_or_size_[right];
        parent_or_size_[right] = left;
        return true;
    }

private:
    std::vector<int> parent_or_size_;
};

unite returns false when both values already share a component. Values must be in [0, count).

二叉堆与堆排序 #

建堆复杂度为 \(O(n)\)；每次 push 或 pop 的复杂度为 \(O(\log n)\)。

cpp

#include <algorithm>
#include <vector>

void heapsort(std::vector<int>& values) {
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());
}

std::sort_heap produces ascending order in-place. Heapsort has \(O(n \log n)\) worst-case time and \(O(1)\) auxiliary storage, but std::sort is the better general-purpose sort.

归并排序与逆序对计数 #

Use std::stable_sort when equal elements must retain their input order. Merge sort costs \(O(n \log n)\) time and \(O(n)\) auxiliary storage.

cpp

#include <algorithm>
#include <vector>

template <class T, class Compare>
void stable_sort_records(std::vector<T>& values, Compare compare) {
    std::stable_sort(values.begin(), values.end(), compare);
}

For inversion counts, merge two sorted ranges and add the number of unmerged left elements whenever the right element is emitted. The resulting algorithm remains \(O(n \log n)\).

素数筛 #

欧拉筛记录每个合数的最小质因子。 Each composite is marked once, giving \(O(n)\) time and \(O(n)\) memory.

cpp

#include <vector>

std::vector<int> least_prime_factors(int limit) {
    std::vector<int> least_prime(limit + 1);
    std::vector<int> primes;

    for (int value = 2; value <= limit; ++value) {
        if (least_prime[value] == 0) {
            least_prime[value] = value;
            primes.push_back(value);
        }
        for (int prime : primes) {
            if (prime > limit / value) {
                break;
            }
            least_prime[prime * value] = prime;
            if (prime == least_prime[value]) {
                break;
            }
        }
    }
    return least_prime;
}

The division guard prevents overflow. Use Eratosthenes for a Boolean primality table and a segmented sieve when the complete range does not fit in memory.

快速选择与快速排序 #

使用标准库的内省算法，因为它们避免快速排序的平方级最坏情况，并且无需对整个范围排序即可完成选择。

cpp

#include <algorithm>
#include <cstddef>
#include <vector>

void sort_values(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
}

int select_nth(std::vector<int>& values, std::size_t rank) {
    std::nth_element(values.begin(), values.begin() + rank, values.end());
    return values[rank];
}

std::sort has \(O(n \log n)\) comparisons. std::nth_element has \(O(n)\) average complexity; rank must be less than values.size(), and neither resulting partition is sorted.