数组操作

[编程题]数组操作

热度指数：13969 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

输入一个无序整数数组，调整数组中数字的顺序，所有偶数位于数组的前半部分，使得所有奇数位于数组的后半部分。
要求时间复杂度为O(n)。

输入描述:

给定无序数组。
长度不超过1000000。

输出描述:

所有偶数位于数组的前半部分，所有奇数位于数组的后半部分。
如果有多个答案可以输出任意一个正确答案。

示例1

输入

2 4 5 7 8 1

输出

2 4 8 7 5 1

备注:

请自觉使用O(n)的算法。

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

const int N = 1E6;

void swap(int* a, int* b) {
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int main(const int argc, const char* const argv[]) {
  int nums[N], numsSize = 0;
  while (fscanf(stdin, "%d", nums + numsSize++) != EOF);  
  --numsSize;
  
  int l = 0, r = numsSize - 1;
  while (l < r) {
    while (l < r && !(*(nums + l) & 1)) ++l;
    while (l < r && *(nums + r) & 1) --r;
    if (l < r) swap(nums + l++, nums + r--);
  }
  
  int i;
  for (i = 0; i < numsSize; ++i)
    fprintf(stdout, "%d ", *(nums + i));
  
  return 0;
}

发表于 2021-07-28 11:20:00 回复(0)