calcolo 10 numeri più ripetuti in un array java

[891]

Salve a tutti, come da titolo qualcuno mi potrebbe aiutare a scrivere un codice java che, dato un array di 100 numeri, ne stami i 10 più frequenti. Ora provo a buttare giu il codice, se mi deste una mano ve ne sarei molto grato. Grazie

 

[AlphaSnake]

puoi utilizzare le collection? come ArrayList, oppure sei costretto ad usare un semplice array?

 

[891]

puoi utilizzare le collection? come ArrayList, oppure sei costretto ad usare un semplice array?

L'ideale sarebbe usando semplici array

 

[AlphaSnake]

Va bene comunque è molto semplice, se non hai vincoli di complessità temporale, prendi il primo elemento e cerchi le sue occorrenze nell'array restante se sono >= 10 stampi il numero altrimenti no, prendi il secondo elemento e fai la stessa cosa e così via. Ovviamente questa è la modalità semplice, non ti scrivo il codice in java o in pseudocodice perché non avrebbe senso, ora che ti ho indirizzato prova a farlo tu.

 

[891]

Va bene comunque è molto semplice, se non hai vincoli di complessità temporale, prendi il primo elemento e cerchi le sue occorrenze nell'array restante se sono >= 10 stampi il numero altrimenti no, prendi il secondo elemento e fai la stessa cosa e così via. Ovviamente questa è la modalità semplice, non ti scrivo il codice in java o in pseudocodice perché non avrebbe senso, ora che ti ho indirizzato prova a farlo tu.

Ok grazie intanto, ci provo e ti faccio sapere

 

[rodhellas]

Usi un array di supporto di

Va bene comunque è molto semplice, se non hai vincoli di complessità temporale, prendi il primo elemento e cerchi le sue occorrenze nell'array restante se sono >= 10 stampi il numero altrimenti no, prendi il secondo elemento e fai la stessa cosa e così via. Ovviamente questa è la modalità semplice, non ti scrivo il codice in java o in pseudocodice perché non avrebbe senso, ora che ti ho indirizzato prova a farlo tu.

Perchè >= 10?

 

[AlphaSnake]

Usi un array di supporto di

Perchè >= 10?

ho riletto il testo, hai ragione ho sbagliato, pensavo che volesse tutti i numeri con minimo 10 occorrenze.l'ideale sarebbe creare o avere una struttura con 2 campi uno chiave e uno che conta le frequenze, alla fine ti stampi i 10 coi valori più grandi facendo un semplice ordinamento discendente.

 

[891]

ho riletto il testo, hai ragione ho sbagliato, pensavo che volesse tutti i numeri con minimo 10 occorrenze.l'ideale sarebbe creare o avere una struttura con 2 campi uno chiave e uno che conta le frequenze, alla fine ti stampi i 10 coi valori più grandi facendo un semplice ordinamento discendente.

Quindi creo una funzione che conta le occorrenze di ogni numero, poi le posso memorizzare in un array, lo ordino e stampo le prime 10? Un'altra domanda.

Se ad esempio ho {12,30,2,30,.....}
conto l'occorrenza del primo 30 e la inserisco nell'array, poi quando la chiave della ricerca sarà il secondo 30, rischio di ripeterlo 2 volte nell'output? Non so se si è capito spero di si.

 

[rodhellas]

Quindi creo una funzione che conta le occorrenze di ogni numero, poi le posso memorizzare in un array, lo ordino e stampo le prime 10? Un'altra domanda.

Se ad esempio ho {12,30,2,30,.....}
conto l'occorrenza del primo 30 e la inserisco nell'array, poi quando la chiave della ricerca sarà il secondo 30, rischio di ripeterlo 2 volte nell'output? Non so se si è capito spero di si.

Se ordini l'array da 100 ( metodo sort ), riduci la complessità della ricerca da O(n! (mi pare :asd:)) a O(n+ costo per ordinarlo). E sei sicuro di non avere ripetizioni.
Ovviamente l'algoritmo funzionerà cosi: inizi con i = 0, finchè l'== è vero vai avanti e incrementi il contatore. Appena diventa !=, salvi i valori fin qui calcolati e il valore da confrontare sarà l'i attuale( ovvero il primo numero != da quello precedente ) con i successivi

 

[AlphaSnake]

io non so se è

Se ordini l'array da 100 ( metodo sort ), riduci la complessità della ricerca da O(n! (mi pare :asd:)) a O(n+ costo per ordinarlo). E sei sicuro di non avere ripetizioni.
Ovviamente l'algoritmo funzionerà cosi: inizi con i = 0, finchè l'== è vero vai avanti e incrementi il contatore. Appena diventa !=, salvi i valori fin qui calcolati e il valore da confrontare sarà l'i attuale( ovvero il primo numero != da quello precedente ) con i successivi

O(n!) eh la madonna ahahahha no al massimo sarebbe O(n^2)
Per quanto mi riguarda l'ordinamento aiuta, in java gli ordinamenti sono già implementati per le strutture dati come Arrays, basta invocare il metodo sort http://forum.html.it/forum/showthread/t-1195438.html
Ora immagino che il metodo sort utilizza un quicksort o un mergesort complessità media quick sort O( n log n) complessità mergesort O(n log n). Una volta ordinato puoi fare mille cose come implementare un arraylist di coppie, ma questo lo potevi fare già prima, dove fai una classe coppia e crei due campi interi uno K e uno V, dove K è l'intero dell'array mentre V è il numero di occorrenze. Infine prendi l'arraylist delle coppie lo ordine in modo decrescente per V e stampi i 10 interi. Poi ci sono altri cento modi, sta a te.Ora la mia domanda è: ma è un esercizio di scuola? che cosa puoi utilizzare, quanto avete fatto?

 

[891]

Allora aggiorno. Ho risolto tutto grazie mille. Un'ultima cosa. Ho creato un oggetto con 2 campi; numero e occorrenze. Come posso ordinare gli oggetti in base alle ripetizioni?
Ho provato modificando insertionSort, potrebbe andare? Coppia è un array di oggetti

void SortOccorrenze(Coppia arr[]) {
  int n = arr.length;
  for (int i = 1; i < n; ++i) {
    int key = arr[i].occorrenze;
    int j = i - 1;

    while (j >= 0 && arr[j].occorrenze> key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1].occorrenze= key;
  }
}

 

[AlphaSnake]

Qui le cose si fanno un po' complicate hai bisogno dell'interfaccia Comparable<T> T è un generico e nel nostro caso ci metti 'Coppia' e poi devi fare l'overriding di CompareTo dove gli dici come fare il sorting, quindi devi dirgli di fare il confronto tra i valori delle occorrenze.Quello che adesso ti consiglio di fare è di googlare e vedere un po' di esempi con CompareTo. Fammi sapere, perché è leggermente complicato.Ti rispondo nel pomeriggio.

 

[Simone Trombiero]

Se i 100 interi non stanno in un range troppo ampio, esiste una soluzione con complessità lineare (ma con alta complessità spaziale presumibilmente, O(max(array))).
Utilizzi un bucket, un array di dimensione max(array), nel quale bucket[j] contiene le occorrenze di j in a.
Lo riempi molto semplicemente in questo modo:

for(int i=0;i<array.length;i++) bucket[array[i]]++;

E non ti resta che calcolare banalmente i 10 massimi di bucket, e prenderne l'indice.

 

[AlphaSnake]

oppure per farla molto facile, usi un ArrayList di supporto, dove lo riempi con gli elementi della Coppia array[]. Una volta fatto ciò, ti vai a stampare l'elemento che ha il massimo valore dell'occorrenza.Ok ora ArrayList ha un metodo per rimuovere quell'elemento 'remove(Object o)' e ricominci prendendo il massimo. Fai questo per 10 volte e hai i 10 numeri.
Questo è molto semplice come algoritmo, ma se vuoi fare le cose più eleganti, usare comparable con compareTo è la soluzione migliore.

 

[AlphaSnake]

Metto la mia soluzione, cerca di spizzarla, come si fa con le carte e capire cosa ho fatto:
Questo è il main:

Spoiler: Main

import java.util.ArrayList;
import java.util.Collections;

public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a = new int [100];
        System.out.println("Questi sono gli elementi:\n");
        for (int i=0;i<100;i++)
        {
            a[i]=((int)(Math.random()*30+1));
            System.out.println(a[i]);
        }
      
        System.out.println("Questi sono gli elementi ordinati:\n");
        OrdinamentoAndMax o = new OrdinamentoAndMax();
        int[] b = o.ordinamento(a);
        System.out.println();
        for (int i=0;i<100;i++)
            System.out.println(b[i]);
        System.out.println("Questi sono le coppie disordinate, con il loro relativo valore di occorrenza \n");        
        ArrayList <Coppia> c = o.occorrenze(b);
        for(int i=0; i<c.size();i++)
        {
            int k = c.get(i).getChiave();
            int v = c.get(i).getValore(k);
            System.out.println(k+" , "+v);
          
        }
      
        System.out.println("Queste sono le coppie ordinate in base al valore di occorrenza");
        Collections.sort(c,new SimpleComparator());
      
        for(int i=0; i<c.size();i++)
        {
            int k = c.get(i).getChiave();
            int v = c.get(i).getValore(k);
            System.out.println(k+" , "+v);
        }
      
        System.out.println("Questi sono i primi 10 valori con maggiore occorrenza \n");
        int j=c.size()-1;
        while(j>=c.size()-10)
        {
         System.out.println(c.get(j).getChiave());
         j--;  
        }
        //questo è opzionale,
        //stampo gli elementi che hanno la stessa occorrenza del decimo
        while(j>0 && c.get(j).getValore()== c.get(j+1).getValore())
        {
            System.out.println(c.get(j).getChiave());
            j--;
        }
      
    }
  
  
  

}

Coppia:

Spoiler: Coppia

public class Coppia
{
    private int k;
    private int v;
   
    public Coppia( int k , int v)
    {
        this.k=k;
        this.v=v;
    }
   
    public void setCoppia(int chiave, int valore)
    {
        k=chiave;
        v=valore;
    }
   
    public int getValore(int k)
    {
        return v;
    }
   
    public int getChiave()
    {
     return k;
    }
    public int getValore()
    {
        return v;
    }
   
   
   
   
}

Ordinamento:

Spoiler: Ordinamento

import java.util.ArrayList;
import java.util.Arrays;


public class OrdinamentoAndMax
{
private int a[];
public void inizializzazione( int b[])
{
     int n = b.length;
     a = new int [n];
     for(int i=0;i<n;i++)
     {
         a[i]=b[i];
     }
}
public int [] ordinamento (int b[])
{
     Arrays.sort(b);
     return b;
}
public ArrayList<Coppia> occorrenze (int b[])
{
     ArrayList<Coppia> c = new ArrayList<Coppia> ();
     for(int i=0;i<b.length;i++)
     {
       int j=i;
       int key=b[i];
       int count=0;
       while((j+count)<b.length && key==b[j+count])
       {
        count++;  
       }
       Coppia cp = new Coppia(key,count);
       c.add(cp);
       i=i+count-1;
     }
     return c;
}





}

Comparator:

Spoiler: Comparator

import java.util.Comparator;

public class SimpleComparator implements Comparator<Coppia>
{



    @Override
    public int compare(Coppia a, Coppia b) {
        // TODO Auto-generated method stub
        Integer v1=a.getValore();
        Integer v2=b.getValore();
        return v1.compareTo(v2);
    }

}