PAT 解题报告 1067. Sort with Swap(0,*) (25)

1067. Sort with Swap(0,*)题目描述:

Given any permutation of the numbers {0, 1, 2,…, N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

题目就是要求只利用和数值0(零)交换的操作Swap(0, *)将打乱的0, 2, 3, …, N-1 排序, 问最少要使用多少次Swap(0, *).

1067. Sort with Swap(0,*)算法分析:

这个题目个人觉得还蛮难的其实, 想了不少时间, 可以这么想: 给打乱的0, 2, 3, …, N-1 排序, 那么最最少的操作肯定是要把那些放错位置的放到正确的位置, 正确的位置的状态是A[i] == i, i = 0, …, N-1, 对于那些已经正确的位置我们不去改变他也不做任何操作(你想我们要是再去动他, 后面还是要把他们放回到正确的位置, 这样会增加不必要的swap, 于是要保证至少我们不应该去改变这些正确位置上的数), 那么如何对那些没有在正确位置的数字通过最少的Swap(0, *)来调整? 我们看这个例子, {4, 0, 2, 1, 3}, A[0] = 4, 那么我们需要把4放到A[4]上面(这是最少的操作, 也就是为了让4到A[4]上我们最最少也要移动一次), 那么连锁反应, A[4]上现在是3, 我们需要把3放到A[3]上, 然而A[3]上现在是1, 我们需要把1放到A[1]上, A[1]上现在是0, 我们需要把0放到A[0]上, 这其实是一个循环, 我们这么表示 A[0]->A[4]->A[3]->A[1]->A[0], 注意这里A[0]是循环节点. 这里面总共有四个数字放错位置, 为了让这四个放错位置的放到正确的位置的话, 我们其实只需要4 – 1 = 3次Swap(0, *) 也就是题目描述中的三次. 这个例子说明这么一个事实: 这样的Swap(0, *) 次数一定是最少需要的次数. 因为我们有四个数放错了位置, 最少也要三次Swap(0, *) , 或者说四次调整. 这一点保证了结果的Swap(0, *) 次数最少.  

同时要是再仔细想想的话我们可以得出下面两个关于A[0]的重要结论:

(1) 如果A[0] != 0, 那么A[0]将是需要调整的数字, 从A[0]开始必然可以找到上述例子中的循环, 然后进行调整, 调整以后A[0] = 0

(2) 如果A[0] == 0, 那么从其他非正确位置的数字开始找到的循环一定不包含A[0], 但是因为我们只能使用Swap(0, *) , 所以需要先把A[0] = 0和非正确位置循环中的数交换, 那么交换以后的情况就变成了(1)的情况, 继续模拟.

利用这些结论模拟Swap(0, *) 直到所有的数字都在各自的正确位置就可以了, 下面是可以AC的代码:

#include <cstdio>
#include <vector>
#include <algorithm>

int swapZero(std::vector<int> &nums) {
    int cnt = 0;
    int tmp1 = 0;
    int tmp2 = nums[tmp1];
    nums[0] = 0;
    while(tmp2 != nums[tmp2]) {
        tmp1 = nums[tmp2];
        nums[tmp2] = tmp2;
        tmp2 = tmp1;
        ++cnt;
    }
    return cnt;
}

int gao(std::vector<int> &nums) {
    int len = nums.size();
    int res = 0;

    for(int i = 0; i < len; ++i) {
        if(nums[i] != i) {
            if(0 != i) {
                std::swap(nums[0], nums[i]);
                res += 1;
            }
            res += swapZero(nums);
        }
    }
    return res;
}

int main() {
    int n;
    std::vector<int>  nums;
    scanf("%d", &n);
    nums.resize(n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &nums[i]);
    printf("%d\n", gao(nums));
    return 0;
}

这个模拟算法的时间复杂度是线性的O(N), 因为所有的没在正确位置的数字都只被调整一次, 调整到了正确位置以后就再也不会有多余操作了. 所以总体的复杂度O(N).

Written on October 13, 2013