Algorithm

[LintCode 373] Partition Array by Odd and Even [C++] [Runtime : 13MS]

顿搜

2017-07-27

0 评论

645 阅读

正在检测是否收录...

07/27

1. Description

Partition an integers array into odd number first and even number second.

2. Submission Details

3. Code

void partitionArray(vector<int>& nums)
{
    if (nums.empty()) {
        return;
    }

    int start = 0, end = nums.size() - 1;

    while (start < end) {

        while (start < end && (nums[start] & 1) == 1)
            start++;
        while (start < end && (nums[end] & 1) == 0)
            end--;
        if (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }
    }
}

4.Test

#include <iostream>
#include <vector>

using namespace std;

class LintCode0373 {
public:
    void partitionArray(vector<int>& nums)
    {
        if (nums.empty()) {
            return;
        }

        int start = 0, end = nums.size() - 1;

        while (start < end) {

            while (start < end && (nums[start] & 1) == 1)
                start++;
            while (start < end && (nums[end] & 1) == 0)
                end--;
            if (start < end) {
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
            }
        }
    }
};

int main()
{
    LintCode0373 lintcode;
    int numbers[] = { 1, 2, 3, 4 };
    vector<int> nums(numbers, numbers + 4);
    lintcode.partitionArray(nums);
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
    }
}

Array

朗读