C++另一个数组中较小值的排列

问题描述

在一个大小为n的数组a中，对于每个i，都有一个较小值在数组b中，且b[i] != a[i]。请找到一个排列p，使得对于每个i，都有b[p[i]]为a[i]的较小值。

解决方案

1.暴力枚举

首先，我们可以暴力枚举所有可能的排列，再验证是否符合题目要求。具体实现可以使用STL中的next_permutation函数，该函数可以依次生成所有的排列。

下面是暴力枚举的示例代码：

bool Check(int *a, int *b, int *p, int n) {
    for (int i = 0; i < n; i++) {
        int x = p[i];
        if (b[x] == a[i]) {
            return false;
        }
    }
    return true;
}
int Solve1(int *a, int *b, int n) {
    int ans = n;
    int *p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    do {
        if (Check(a, b, p, n)) {
            ans = min(ans, InversePairs(p, n));
        }
    } while (next_permutation(p, p + n));
    delete[] p;
    return ans;
}

但是，暴力枚举时间复杂度为O(n!)，当n较大时，该算法的运行时间是很长的。

2. 基于逆序对的归并排序

由于暴力枚举是非常低效的，我们需要寻找更加高效的算法。我们可以发现，对于一个排列p，如果b[p[i]] <= a[i]，那么该排列就不符合题目要求。

因此，我们可以通过对数组a和b排序，同时记录b中每个元素在原数组中的位置，得到每个a[i]对应的较小值在b中的位置q[i]，然后求解q的逆序对数即可。

下面是具体实现的示例代码：

bool cmp(const int& a, const int& b) {
    return a > b;
}
int Solve2(int *a, int *b, int n) {
    int ans = n;
    int *q = new int[n];
    for (int i = 0; i < n; i++) {
        q[i] = lower_bound(b, b + n, a[i], cmp) - b;
    }
    ans = InversePairs(q, n);
    delete[] q;
    return ans;
}

由于逆序对问题可以通过归并排序求解，因此我们可以使用归并排序优化复杂度。下面是基于逆序对的归并排序的示例代码：

int Merge(int *a, int *b, int l, int mid, int r) {
    int i = l, j = mid + 1;
    int k = l, cnt = 0;
    while (i <= mid && j <= r) {
        if (a[i] > a[j]) {
            cnt += mid - i + 1;
            b[k++] = a[j++];
        } else {
            b[k++] = a[i++];
        }
    }
    while (i <= mid) {
        b[k++] = a[i++];
    }
    while (j <= r) {
        b[k++] = a[j++];
    }
    for (i = l; i <= r; i++) {
        a[i] = b[i];
    }
    return cnt;
}
int MergeSort(int *a, int *b, int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid = (l + r) >> 1;
    int cnt = MergeSort(a, b, l, mid) + MergeSort(a, b, mid + 1, r);
    cnt += Merge(a, b, l, mid, r);
    return cnt;
}
int InversePairs(int *a, int n) {
    int *b = new int[n];
    int cnt = MergeSort(a, b, 0, n - 1);
    delete[] b;
    return cnt;
}

总结

本文介绍了C++中另一个数组中较小值的排列问题，并给出了两种解决方案：暴力枚举和基于逆序对的归并排序。实际应用中，基于逆序对的归并排序是更加高效的算法，其时间复杂度为O(nlogn)。