Q005_ryanorz_solution

[ryanorz]

Question_ID: Q005

Language: c++

Time Cost: 40-mins + 40mins

Time Complexity: O(n)

Solution

1. 先对整个序列做中位数划分
2. 分别对左右区域做中位数划分
3. 将右侧区域往左侧区域插入

My Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>

using std::cout;
using std::endl;
using std::vector;

class Fluctuation
{
    void mid_element(vector<int>::iterator beginIter, vector<int>::iterator endIter)
    {
        if (endIter < beginIter)
            return;
        auto midIter = beginIter + (endIter-beginIter)/2;
        std::nth_element(beginIter, midIter, endIter);
    }
public:
    void fluctuation(vector<int> &nums)
    {
        auto size = nums.size();
        if (size < 2)
            return;
        auto midIter = nums.begin() + (nums.end()-nums.begin())/2;
        mid_element(nums.begin(), nums.end());
        mid_element(nums.begin(), midIter);
        mid_element(midIter+1, nums.end());

        auto midIndex = (nums.size()-1)/2;

        // 方法1： 初始方案，移动次数很多
//        for (auto i = midIndex+1; i < size; ++i) {
//            auto target = (i - midIndex) * 2 - 1;
//            for (auto j = i; j > target; --j) {
//                std::swap(nums[j], nums[j-1]);
//            }
//        }
        // 方法2： 循环交换元素方案只需要交换 n-1 次
        size_t index = 1;
        int num = nums[index];
        while (index < size) {
            size_t target = (index <= midIndex) ? 2*index : (index-midIndex)*2-1;
            int temp = nums[target];
            nums[target] = num;
            index = target;
            num = temp;
            if (index == 1)
                break;
        }
    }

    bool test(const vector<int> &nums)
    {
        auto size = nums.size();
        if (size < 2) return true;
        for (auto i = 0; i < size-1; ++i) {
            if (nums[i] == nums[i+1]) return false;
            if ((bool)(i&1) ^ (nums[i] > nums[i+1])) return false;
        }
        return true;
    }
};

int main() {
    Fluctuation solution;

    vector< vector<int> > testcases = {
            {},
            {1},
            {1, 2},
            {1, 1, 2},
            {1, 1, 2, 2},
            {1, 1, 2, 2, 3},
            {1, 1, 1, 2, 2, 2},
    };
    auto seed = std::chrono::system_clock::now().time_since_epoch().count();
    for (auto& testcase : testcases) {
        if (testcase.size() >= 2) {
            shuffle (testcase.begin(), testcase.end(), std::default_random_engine(seed));
        }
        for_each(testcase.begin(), testcase.end(), [](int x) { cout << x << " ";});
        cout << endl;

        solution.fluctuation(testcase);
        if (!solution.test(testcase))
            cout << "error" << endl;

        for_each(testcase.begin(), testcase.end(), [](int x) { cout << x << " ";});
        cout << endl;
        cout << "-------------" << endl;
    }

    return 0;
}

Other

算法想了40分钟，实现测试40分钟.这个算法用脑子想觉得逻辑上是可以的，测试用例也都没问题，严格数学上证明，我不会，囧