主页 / 问题 / 1256275
Accepted
Максим Филимонов
Asked:2022-03-15 23:28:10 +0000 UTC2022-03-15 23:28:10 +0000 UTC

重新排列数组中的数字

  • 772
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long arr1[n];
    for (int i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    for (int i = 0; i < n; i++) {
        for (int k = i; k < n; k++) {
            if (arr1[k] % 2 == 0) {
                long long t = arr1[k];
                arr1[k] = arr1[i];
                arr1[i] = t;
            }
        }
        cout << arr1[i] << " ";
    }
}

有必要重新排列数组中的偶数和奇数，使偶数在开头，奇数仅在它们之后。必须保持顺序

数字已重新排列，但顺序未保留，请帮助

c++

3 个回答

  1. Best Answer

    它是 C++，所以在一行中 -

    stable_sort(arr1,arr1+n,[](auto a, auto b) { return abs(a)%2 < abs(b)%2; });

    如果我理解正确，您的“必须保留序列”...

    • 3 
  2. #include <iostream>

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


using namespace std;

void print_arr (long long a[], size_t n)
{
  for (size_t i = 0, j = 0; i < n; i++)
    cout << a[i] << ' ';
  cout << '\n';
}

int main() {
  int n;
  cin >> n;
  long long arr1[n];
  for (int i = 0; i < n; i++) {
    arr1[i] = random() % 100;
    if (random() % 100 > 49)
      arr1[i] = -arr1[i];
  }

  print_arr(arr1, n);

  long long *t = (__typeof__(t))malloc(n * sizeof(t[0]));
  size_t j = 0, k = 0;
  for (size_t i = 0; i < n; i++) 
    if (arr1[i] & 1LL) // odd number
      t[k++] = arr1[i];
    else
      arr1[j++] = arr1[i];

  print_arr(arr1, j);
  print_arr(t, k);

  for (size_t i  = 0; j < n; j++)
    arr1[j] = t[i++];
  free(t);
  
  print_arr(arr1, n);

  return puts("End") == EOF;
}
    • 1

  3. 如果有额外的内存，stable_partition 在线性时间内解决问题，如果没有，则在 NlogN 中解决。

    // g++ -std=c++11 -pedantic -Wall -Wextra -Werror stable-partition.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    std::vector<long long> a;

    std::copy_n(
        std::istream_iterator<long long>(std::cin),
        n,
        std::back_inserter(a)
    );

    std::stable_partition(
        a.begin(),
        a.end(),
        [](long long v) { return v % 2 == 0; }
    );

    std::copy(
        a.begin(),
        a.end(),
        std::ostream_iterator<long long>(std::cout, " ")
    );
    std::cout << '\n';
}

    $ g++ -std=c++11 -pedantic -Wall -Wextra -Werror stable-partition.cpp
$ echo 11 1 2 3 4 5 6 7 8 9 -1 -2 | ./a.out 
2 4 6 8 -2 1 3 5 7 9 -1

    一些笔记

    标准 C++ 不包含可变长度数组。long long arr1[n];这是关于一个n不是常量的字符串。GCC 支持它们作为扩展，但vector在这里更合适。

    既然我们这里有这么一个C++，那么在没有循环的情况下读/写数组也更符合逻辑。

    • 1

相关问题