Ho risolto l'esercizio e posto il codice per tutti quelli che ne avranno bisogno in futuro.

La logica utilizzata è basata sull'appoggiarsi a un secondo array, inizialmente riempito di 0,
di dimensione più grande di 1 del massimo elemento di a[]. Posto il codice così sarà chiaro.
codice:
#include <iostream>

using namespace std;

void conta(int a[],int k[],int na,int nk){

    for(int i=0;i<nk;i++)
        k[i]=0;

    for(int i=0;i<na;i++)
        k[a[i]]++;// nel secondo array alla posizione 2 saranno salvate le occorrenze del 2 e così via

}

int main(){

    int k[4];//la dimensione dell'array di appoggio è +1 rispetto al massimo elemento di a[]

    int a[]={1,2,3,0,3,3,3,2,1};//Il massimo elemento è 3

    conta(a,k,9,4);

    for(int i=0;i<4;i++)
        cout << i << ": " << k[i] << "\n";

    return 0;
}