經典算法題精講：Top-K最小元素、最大子數組和、字符串全排列、數組循環移位

問題一：最小K個數

方案一：改進快速選擇 O(N) 平均，修改原數組

void quick_select(vector& a, int l, int r, int k) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[l + rand() % (r-l+1)];
    while (i <= j) {
        while (a[i] < pivot) ++i;
        while (a[j] > pivot) --j;
        if (i <= j) swap(a[i++], a[j--]);
    }
    if (k <= j) quick_select(a, l, j, k);
    else if (k > i) quick_select(a, i, r, k);
    // 否則 [l..k-1] 即為最小K個
}

方案二：大根堆 O(N log K) 不修改原數組，適合海量數據流

vector top_k(const vector& a, int k) {
    if (k >= a.size()) return a;
    priority_queue max_heap(a.begin(), a.begin() + k);
    for (size_t i = k; i < a.size(); ++i) {
        if (a[i] < max_heap.top()) {
            max_heap.pop();
            max_heap.push(a[i]);
        }
    }
    vector res;
    while (!max_heap.empty()) { res.push_back(max_heap.top()); max_heap.pop(); }
    return res;
}

問題二：連續子數組最大和（最大子段和）

Kadane算法 O(N) 一掃即得：

int max_subarray(const vector& a) {
    int best = INT_MIN, cur = 0;
    for (int x : a) {
        cur = max(x, cur + x);  // 要么延續，要么重新開始
        best = max(best, cur);
    }
    return best;
}

核心洞察：前綴和為負則拋棄（拖累後續），為正則保留（可能增長）。

擴展：輸出區間端點

pair max_subarray_range(const vector& a) {
    int best = INT_MIN, cur = 0, start = 0, best_l = 0, best_r = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (cur <= 0) { cur = a[i]; start = i; }
        else cur += a[i];
        if (cur > best) { best = cur; best_l = start; best_r = i; }
    }
    return {best_l, best_r};
}

問題三：字符串全排列（遞歸交換法）

void permute(string& s, int l, int r, vector& res) {
    if (l == r) { res.push_back(s); return; }
    for (int i = l; i <= r; ++i) {
        // 去重：若s[i]在[l,i-1]中出現過則跳過
        bool dup = false;
        for (int j = l; j < i; ++j) if (s[j] == s[i]) { dup = true; break; }
        if (dup) continue;
        swap(s[l], s[i]);
        permute(s, l+1, r, res);
        swap(s[l], s[i]); // 回溯恢復
    }
}

時間複雜度 O(N!·N)，空間 O(N) 遞歸棧 + O(N!) 結果存儲。

問題四：數組循環左移K位（原地三次逆序）

void reverse(int a[], int l, int r) {
    while (l < r) swap(a[l++], a[r--]);
}

void rotate_left(int a[], int n, int k) {
    k %= n; if (k < 0) k += n;
    reverse(a, 0, k-1);      // 逆序前K
    reverse(a, k, n-1);      // 逆序後N-K
    reverse(a, 0, n-1);      // 逆序整體
}
// 例：1234567 左移3 → 4567123

循環右移K = 左移N-K，或調整逆序順序：

void rotate_right(int a[], int n, int k) {
    k %= n; if (k < 0) k += n;
    reverse(a, n-k, n-1);    // 逆序後K
    reverse(a, 0, n-k-1);    // 逆序前N-K
    reverse(a, 0, n-1);      // 逆序整體
}

複雜度對比總結