Buone soluzioni C++ agli interrogatori "Portare tutti gli zeri sul retro dell'array"

Question

Ho avuto un'intervista per un lavoro di sviluppo Jr. e mi ha chiesto di scrivere una procedura che richiede una serie di intarsi e spinge gli zeri alla schiena. Qui ci sono i vincoli (che lui non mi ha detto all'inizio .... Come spesso accade nelle interviste di programmazione, ho imparato i vincoli del problema, mentre ho risolto lol):

• dovuto farlo a posto; senza la creazione di array temporaneo, nuovi array, ecc
• Non è necessario conservare l'ordine dei numeri diversi da zero (Vorrei che avrebbe fatto mi ha detto questo, all'inizio)

Setup:

int arr[] = {0, -2, 4, 0, 19, 69}; 
/* Transform arr to {-2, 4, 19, 69, 0, 0} or {69, 4, -2, 19, 0, 0} 
    or anything that pushes all the nonzeros to the back and keeps 
    all the nonzeros in front */ 

La mia risposta:

bool f (int a, int b) {return a == 0;} 
std::sort(arr, arr+sizeof(arr)/sizeof(int), f); 

Quali sono alcune altre buone risposte?

Answer 1

Forse l'intervistatore era alla ricerca di questa risposta:

#include <algorithm> 
//... 
std::partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; }); 

Se l'ordine deve essere preservato, quindi std::stable_partition deve essere utilizzato:

#include <algorithm> 
//... 
std::stable_partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; }); 

Per pre C++ 11:

#include <functional> 
#include <algorithm> 
//... 
std::partition(arr, arr + sizeof(arr)/sizeof(int), 
       std::bind1st(std::not_equal_to<int>(), 0)); 

Live Example

Fondamentalmente, se la situazione è che è necessario spostare elementi che soddisfano una condizione su "un lato" di un contenitore, le funzioni dell'algoritmo di partizione dovrebbero essere in alto nell'elenco delle soluzioni da scegliere (se non lo il soluzione da usare).

Answer 2

Un approccio che ordina è O (N * Log N). C'è una soluzione lineare che va in questo modo:

• Impostare due puntatori - readPtr e writePtr, inizialmente indicando l'inizio della matrice
• Fare un ciclo che cammina readPtr l'array fino alla fine. Se *readPtr non è zero, copia su *writePtr e avanza entrambi i puntatori; in caso contrario, anticipare solo readPtr.
• Una volta che readPtr si trova alla fine dell'array, camminare writePtr fino alla fine dell'array, mentre si scrivono gli zeri sugli elementi rimanenti.

Answer 3

Questo è O (n) quindi potrebbe essere quello che sta cercando:

auto arrBegin = begin(arr); 
const auto arrEnd = end(arr); 

for(int i = 0; arrBegin < arrEnd - i; ++arrBegin){ 
    if(*arrBegin == 0){ 
     i++; 
     *arrBegin = *(arrEnd - i); 
    } 
} 
std::fill(arrBegin, arrEnd, 0);