Переставить нули в конец массива

511
13 января 2017, 09:18

Нужно переставить в конец нулевые элементы, не меняя порядок ненулевых. нулевые элементы получается переставить в конец, но порядок ненулевых элементов не сохраняется. как исправить?

n=7
2 0 3 4 0 0 8
8 3 2 4 0 0 0 Для продолжения нажмите любую клавишу . . .
int a; //переменная для хранения значения перестановки
for (i = 0; i < n; i++)
{
    for (int j = i + 1; j < n; j++)
    {
        if (mas[j] == 0)
        {
            a = mas[j];
            mas[j] = mas[i];
            mas[i] = a;
        }
    }
}

for (i = n-1; i >=0; i--)
{
    cout << mas[i] << " ";
}
Answer 1

Имеется стандартный алгоритм std::stable_partition, объявленный в заголовочном файле <algorithm>, который позволяет выполнить задачу в одну строчку.

Ниже представлена демонстрационная программа

#include <iostream>
#include <algorithm>
#include <iterator>
int main()
{
    int a[] = { 2, 0, 3, 4, 0, 0, 8 };
    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;
    std::stable_partition(std::begin(a), std::end(a), 
        [](int x) { return x != 0; });
    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;
}

Ее вывод на консоль:

2 0 3 4 0 0 8
2 3 4 8 0 0 0

Если вам нужно решить задачу с помощью циклов, то можно, например, использовать такой прямолинейный подход, перебирая элементы с конца массива

#include <iostream>
int main()
{
    int a[] = { 2, 0, 3, 4, 0, 0, 8 };
    const size_t N = sizeof(a) / sizeof(*a);
    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;
    for (size_t i = N, m = N; i != 0; i--)
    {
        if (a[i] == 0)
        {
            int item = a[i - 1];
            for (size_t j = i; j != m; j++)
            {
                a[j - 1] = a[j];
            }
            a[--m] = item;
        }
    }
    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;
}

Вывод этой программы на консоль будет таким же, как показано выше:

2 0 3 4 0 0 8
2 3 4 8 0 0 0
Answer 2

Отсортировать :) При условии что функция сортировки сохраняет порядок равных элементов. Будем считать что первый из сравниваемых элементов больше второго если первый не ноль, а второй ноль, и наоборот. Если оба элемента нулевые или не нулевые - они равны.

#include <stdio.h>
#include <stdlib.h>
static int cmp( const void *a, const void *b )
{
    int aa = *(int *)a;
    int bb = *(int *)b;
    if( !aa && bb ) return 1;
    if( aa && !bb ) return -1;
    return 0;
}
static void p( const char *prefix, const int *a, size_t size )
{
    size_t i;
    printf( "%-8s: ", prefix );
    for( i = 0; i < size; i++ ) {
        printf( "%d ", a[i] );
    }
    printf( "\n" );
}
int main(void)
{
    static int a[] = { 8, 0, 3, 4, 0, 0, 2 };
    p( "before", a, sizeof(a)/sizeof(a[0]) );
    qsort( a, sizeof(a)/sizeof(a[0]), sizeof(a[0]), cmp );
    p( "after", a, sizeof(a)/sizeof(a[0]) );
    return 0;
}

Вывод:

before  : 8 0 3 4 0 0 2 
after   : 8 3 4 2 0 0 0 
Answer 3

Довольно простой линейный алгоритм:

  1. Проходим по массиву, все ненулевые элементы двигаем к началу.
  2. Оставшийся хвост заполняем нулями.

http://ideone.com/KHX3Ai

#include <iostream>
using namespace std;
int main()
{
    int a[] = {2, 0, 3, 4, 0, 0, 8};
    const size_t n = sizeof a / sizeof (int);
    size_t i;
    for (size_t q=i=0; q<n; ++q)
        if (a[q])
            a[i++] = a[q];
    for (; i<n; ++i)
        a[i] = 0;
    for (size_t q=0; q<n; ++q)
        cout << a[q] << ' ';
    return 0;
}
READ ALSO
Хранение даты не в UTC

Хранение даты не в UTC

Подскажите, на какие подводные камни можно наткнуться, если хранить дату не в часовом поясе UTC а в каком-либо другом (местном)? Везде, где я читал...

303
Как сформировать запрос в mysql, для вывода месяцев из базы?

Как сформировать запрос в mysql, для вывода месяцев из базы?

Есть таблица, в которой хранятся записи финансовых операцийПервая запись сделана к примеру в ноябре: 2016-11-10 Последняя запись сделана в апреле:...

312
Как скачать базу даных Википедии?

Как скачать базу даных Википедии?

Как скачать базу даных Википедии (английской) для того, чтобы в SQL Management Studio можно было с базой даных работать?

314