前传

求助一下两份代码的复杂度正确性:

swap 思路: 将相等的全部 swap 走.

这一份时间复杂度很小概率假: 峰值时间 166ms

#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5 + 2;

int n, a[kN], b[kN];
map<int, int> bt, ct;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bt[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        ct[b[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (bt[a[i]] + ct[a[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (bt[b[i]] + ct[b[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    cout << "Yes\n";
    reverse(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            reverse(b + i, b + n + 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            for (int j = 1; j <= n; j++) {
                if (a[j] != b[i] && b[i] != b[j]) {
                    swap(b[i], b[j]);
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }

    return 0;
}

这一份时间复杂度很大概率假: 峰值时间 991ms

#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5 + 2;

int n, a[kN], b[kN];
map<int, int> bt, ct;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bt[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        ct[b[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (bt[a[i]] + ct[a[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (bt[b[i]] + ct[b[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    cout << "Yes\n";
    reverse(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            for (int j = 1; j <= n; j++) {
                if (a[j] != b[i] && b[i] != b[j]) {
                    swap(b[i], b[j]);
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }

    return 0;
}