Q005_dploop_solution

[rbee3u]

Question_ID: Q005

Language: C++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

和Q004一样的下标映射思路，刚好把相邻的两个数间隔到数组大小的一半距离。不过由于这里的要求是严格不等，所以单纯的两路划分不行，改成了三路划分。至于三路划分为什么可以，我想到了一种绝妙的证明方法，不过这里的空白太小写不下。

My Code

#include <algorithm>
#include <iostream>
#include <vector>

void fluctuation(std::vector<int>& X) {

    int n = X.size();

    #define Y(i) X[(2*(i) + 1) % (n | 1)]

    nth_element(X.begin(), X.begin()+n/2, X.end());

    int pivot = X[n/2];

    int lo = 0, hi = n - 1,  mid = 0;
    while (mid <= hi) {
        if (Y(mid) > pivot) {
            std::swap(Y(lo++), Y(mid++));
        } else
        if (Y(mid) < pivot) {
            std::swap(Y(mid), Y(hi--));
        } else {
            mid++;
        }
    }
}

int main() {

    std::vector<int> X{1, 1, 1, 1, 2, 2, 2};

    fluctuation(X);

    for (int x : X) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Other

[isaacpei]

d师d师你为啥这么强啊 带我飞吧