Q004_ryanorz_solution

[ryanorz]

Question_ID: Q004

Language: c++

Time Cost: 30-mins

Time Complexity: O(n)

Solution

1. 三个元素一组，排序成“小大小”
2. 第一组最后一个和之后两个再组成三个数的组，重复步骤１
3. 最后剩一个数，构不成三个数的组，就排成“小大”

My Code

#define CATCH_CONFIG_MAIN
#include <iostream>
#include <vector>
#include <algorithm>
#include "catch.hpp"

using namespace std;

void fluctuation(vector<int>& nums) {
    int size = nums.size();
    int flag = true;
    for (int i = 0; i < size-1; i++) {
        if ((flag && nums[i] > nums[i+1]) ||
            (!flag && nums[i] < nums[i+1])) {
            swap(nums[i], nums[i+1]);
        }
        flag = !flag;
    }
}

bool result_check(vector<int>& nums) {
    int size = nums.size();
    bool flag = true;
    for (int i = 0; i < size-1; i++) {
        if (flag) {
            if (nums[i] <= nums[i+1]) {
                flag = !flag;
            } else {
                return false;
            }
        } else {
            if (nums[i] >= nums[i+1]) {
                flag = !flag;
            } else {
                return false;
            }
        }
    }
    return true;
}

TEST_CASE("fluctuation", "fluctuation") {
    WHEN("empty") {
        vector<int> nums = {};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("1 element") {
        vector<int> nums = {1};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("2 elements") {
        vector<int> nums = {1, 2};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("3 elements") {
        vector<int> nums = {1, 2, 3};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("4 elements") {
        vector<int> nums = {1, 2, 3, 4};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("5 elements") {
        vector<int> nums = {1, 2, 3, 4, 5};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("sample case") {
        vector<int> nums = {5, 2, 4, 5, 6, 7};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
}

Other

[isaacpei]

牛逼牛逼我服我服