雜項演算法

當標準函式庫演算法的契約符合工作需求時，請使用它們，因為其實作會針對目標平台進行最佳化。

左側最近較小元素 #

在堆疊上維持遞增值。每個索引各推入與彈出一次，因此時間複雜度為 \(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;
}

當相等的前驅有效時，使用 > 而不是 >=。反轉掃描方向或比較運算會產生下一個較大值、股票跨度、直方圖與溫度查詢等變體。

不相交集合聯集 #

按大小合併與路徑折半會使 find 與 unite 的攤銷複雜度達到 \(O(\alpha(n))\)。負值項目儲存根的元件大小。

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 會傳回 false。值必須位於 [0, count)。

二元堆積與堆積排序 #

建立堆積為 \(O(n)\)；每次推入或彈出為 \(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 會就地產生遞增順序。堆積排序的最壞情況時間為 \(O(n \log n)\)，輔助儲存空間為 \(O(1)\)，但 std::sort 是更好的通用排序。

合併排序與反轉計數 #

當相等元素必須保留輸入順序時，使用 std::stable_sort。合併排序的時間為 \(O(n \log n)\)，輔助儲存空間為 \(O(n)\)。

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);
}

計算反轉數時，合併兩個已排序範圍，並在輸出右側元素時加入尚未合併的左側元素數量。產生的演算法仍為 \(O(n \log n)\)。

質數篩 #

Euler 篩會記錄每個合數的最小質因數。每個合數只標記一次，因此時間為 \(O(n)\)，記憶體為 \(O(n)\)。

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;
}

除法防護可避免溢位。布林質數表使用 Eratosthenes 篩，當完整範圍無法放入記憶體時使用分段篩。

Quickselect 與 Quicksort #

請使用內省式標準函式庫演算法，因為它們避免 quicksort 的二次方最壞情況，並能在不排序完整範圍的情況下進行選取。

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 需要 \(O(n \log n)\) 次比較。std::nth_element 的平均複雜度為 \(O(n)\)；rank 必須小於 values.size()，且產生的兩個分割區都未排序。