Q004_dploop_solution

[rbee3u]

Question_ID: Q004

Language: C++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

类似于快排的划分思路，先找到中位数(这个我直接调用的STL库函数，理论上寻找中位数是可以达到最坏为O(n)的，STL的实现最坏不一定保证但平均应该为O(n))，接着就是用这个中位数进行划分。 和快排不一样的地方是，快排的划分是小于中位数的划分到数组前半段，大于中位数的划分到数组后半段。而这道题的话，则是小于中位数的划分到数组偶数编号，大于中位数的划分到数组奇数编号。为了达到这个目标最简单的方式就是用宏做了个下标映射。

为什么用了40分钟，主要是下标映射的时候卡了好久(我想把前一半下标映射到偶数上，一直没成功)，一时半会儿没转过弯来。

My Code

#include <algorithm>
#include <iostream>

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;
    while (lo < hi) {
        if (Y(lo) >= pivot) {
            ++lo;
        } else
        if (pivot >= Y(hi)) {
            --hi;
        } else {
            std::swap(Y(lo), Y(hi));
        }
    }
}

int main() {

    std::vector<int> X{5, 2, 4, 5, 6, 7};

    fluctuation(X);

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

    return 0;
}

Other

[rbee3u]

看了前两位的解答，感觉我又想复杂了。。。orz

[isaacpei]

讲真... 我想要的是这种答案...

[rbee3u]

如果是要 > 而不是 >= 的话，可以把二路划分改成三路划分