Удаление всех единиц из массива

#массивы #алгоритм

Всем привет!

Мне тут задали очень "простую" задачку на интервью, которая буквально поставила меня
в ступор. Есть у кого идеи, как можно решить? Интервью я уже пролетел, но очень интересно
таки понять правильное решение. К ЯП можно не привязываться.

Задачка следующая:

Дан вектор интов(или массив, как угодно). Удалить из него все единицы с сохранением
порядка остальных членов за O(n), используя O(1) дополнительной памяти.
    

Ответы

Ответ 1

Да проблем-то... Два указателя. Один - на текущий рассматриваемый элемент, второй
- на место для его записи. Изначально они указывают на первый элемент. Дальше просто
идем и смотрим - что там.

Не 1 - копируем (если указатели не совпадают), перемещаем оба указателя.

1 - перемещаем просто указатель дальше...

Вот рабочий код:

int main(int argc, const char * argv[])
{
    int a[30];
    for(int i = 0; i < 30; ++i) a[i] = rand()%10;


    for(int i = 0; i < 30; ++i) cout << a[i] << " "; cout << endl;


    int j = 0;
    for(int i = 0; i < 30; ++i)
    {
        if (a[i] != 1) if (i != j) a[j++] = a[i];
    }

    for(int i = 0; i < j; ++i) cout << a[i] << " "; cout << endl;

}