Zählung wiederholt Elemente in einem Array

Question

Zählung wiederholt Elemente in einem Array ..... Eingang {1,1,1,1,2,2,2,3,3,4} Ausgang

1=4 
2=3 
3=2 
4=1 

Answer 1

ist eine gute Methode ist durch die Elemente in dem Array iterieren und zählen, wie viele von jedem, die du siehst. Sobald Sie fertig sind, drucken Sie die Anzahl, die Sie erhalten haben.

Answer 2

prev = input[0]; 
count = 1; 
for (i = 1; i < ARRAYSIZE; i++) 
{ 
    if (input[i] == prev) count++; 
    else 
    { 
    printf("%d=%d ", prev, count); 
    prev = input[i]; 
    count = 1; 
    } 
} 
// Printing the last element 
printf("%d=%d ", prev, count); 

Answer 3

Es scheint, dass das Array sortiert ist (nach dem Beispiel). In diesem Fall müssen Sie nur das erste Element auswählen und das Array durchlaufen, bis ein bestimmter Wert gefunden wird. Innerhalb dieses Prozesses können Sie einen Zähler innerhalb der Schleife haben, um die Vorkommen zu zählen.

Wählen Sie dann den gefundenen eindeutigen Wert anstelle des ersten Elements und wiederholen Sie den Vorgang.

Answer 4

wenn es ist bereits sortiert, kann es einen schnelleren Weg

Split die Liste in zwei Hälften sein. gehe mit jedem Abschnitt auf diese Weise um: teste den ersten und letzten nubmer. Wenn sie gleich sind, kennen Sie das Ergebnis. Wenn es nicht das gleiche ist, teilen Sie es in der Mitte und wiederholen Sie jede Hälfte erneut.

Mit langen Läufen der gleichen Nummer wird dies effizient sein. Wenn ein Abschnitt klein ist, sollte er auf die Eins-zu-Eins-Methode zurückgesetzt werden. Sie könnten die Daten an zufälligen Stellen abtasten und s, s + 1 testen, um einen Prozentsatz der Zeit zu erhalten, die eine Zahl von ihrem Vorgänger ansteigt. Je höher die Zahl ist, desto früher sollten Sie zu einer Methode nach der anderen wechseln.

Diese Methode ist auch parallelisierbar.

Answer 5

Wenn der Bereich der Werte klein ist, können Sie ein anderes Array haben, das die Anzahl jedes Elements enthält, ungefähr so ​​wie counting sort. Wenn der Wertebereich groß ist, benötigen Sie eine hash table.

Answer 6

void count_elements(int * pArray, long nElements) 
{ 
    int * pStart; 
    for (pStart = pArray++; nElements > 1; nElements--, pArray++) 
    { 
     if (*pStart != *pArray) 
     { 
      printf("%i = %u ", *pStart, (pArray - pStart)); 
      pStart = pArray; 
     } 
    } 
    printf("%i = %u ", *pStart, (pArray - pStart)); 
} 

Answer 7

Einfaches Beispiel erklärt.

// jedes Element Count eine sortierte Hash erstellen jedes einzelnes Element aus dem ursprünglichen Array zu halten (auch als verkettete Liste getan werden könnte) jedes Element aus dem Array gelesen wenn das Hash-Element existiert bereits die Zählung erhöhen (Wert) des Schlüssel wenn das Hash-Element existiert nicht ein Schlüsselwertpaar erstellen (Wert = 1) loop

// Drucke jedes Element Schleife durch den Schlüssel der des Hash und printf ("% d: % d \ n ", Schlüssel, Wert); wenn Sie brauchen auch Nullwerte darstellen, einen lastKey implementieren und einen Schlüssel zum lastKey Vergleich zu tun, wenn ein Schlüssel Null

war

Sortieren und einfaches Programm/Funktion

Answer 8

behandelt zu bestimmen:
1) Ende Array Artikel
2) leer Fall
3) Singletons Fall

#include <stdio.h> 

int main() { 

    int input[] = {1,1,1,1,2,2,2,3,3,4}; 

    if (sizeof(input) == 0) return 0; 

    int prev = input[0]; 
    int count = 1; 
    int i; 
    int ARRAYSIZE = sizeof(input)/sizeof(int); 

    for (i = 1; i < ARRAYSIZE; i++) { 
    if (input[i] == prev) { 
     count++; 
    } else { 
     printf("%d=%d ", prev, count); 
     prev = input[i]; 
     count = 1; 
    } 

    } 
    printf("%d=%d\n", prev, count); 
    return 0; 
} 

und die Testfälle:

when input is {} 
----------------------------------- 
jianlin@ubuntu:~$ gcc try.c 
jianlin@ubuntu:~$ ./a.out 

when input is {123} 
----------------------------------- 
jianlin@ubuntu:~$ gcc try.c 
jianlin@ubuntu:~$ ./a.out 
123=1 

when input is {1,123} 
----------------------------------- 
jianlin@ubuntu:~$ gcc try.c 
jianlin@ubuntu:~$ ./a.out 
1=1 123=1 

when input is {1,1,1,1,2,2,2,3,3,4} 
----------------------------------- 
jianlin@ubuntu:~$ gcc try.c 
jianlin@ubuntu:~$ ./a.out 
1=4 2=3 3=2 4=1 

when input is {1,1,1,1,2,2,2,3,3,4,4} 
----------------------------------- 
jianlin@ubuntu:~$ gcc try.c 
jianlin@ubuntu:~$ ./a.out 
1=4 2=3 3=2 4=2