剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目

代码

#include <iostream>
#include <vector>
using namespace std;

// 方法一：超出时间限制 
vector<int> exchange1(vector<int>& nums) {
    
	int n = nums.size();
	if(n == 0 || n == 1){
    
		return nums;
	}
	for(int i = 0; i < n - 1; i++){
    
		if(nums[i] % 2 == 1){
    
			continue;
		}
		for(int j = i + 1; j < n; j++){
    
			if(nums[j] % 2 == 1){
    
				int temp = nums[i];
				nums[i] = nums[j];
				nums[j] = temp;
				break;
			}
		}
	}
	return nums;
}

// 方法二：利用数组，奇数从前往后存，偶数从后往前存 
vector<int> exchange(vector<int>& nums) {
    
	int n = nums.size();
	if(n == 0 || n == 1){
    
		return nums;
	}
	vector<int> res (n);
	int j = 0, k = n - 1;
	for(int i = 0; i < n; i++){
    
		if(nums[i] % 2 == 1){
    
			res[j++] = nums[i];
		}else{
    
			res[k--] = nums[i];
		}
	}
	return res;
}

int main(){
    
	int n;
	cin>>n;
	vector<int> nums(n);
	vector<int> res;
	for(int i = 0; i < n; i++){
    
		cin>>nums[i];
	}
	res = exchange(nums);
	for(int i = 0; i < res.size(); i++){
    
		cout<<res[i]<<" ";
	}
	return 0;
}