Inserire elemento da ArrayList con ordine crescente e senza elementi duplicati

Question

ho un compito a casa dove ho bisogno di inserire o aggiungere nuovi elemment in ArrayList<Interger> con condizioni seguenti:

1. elemento deve ordine crescente.

2. Nessun duplicati elementi nel metodo ArrayList<Integer>

3. inserto corsa in O (n) volte.

Ecco il mio metodo di inserimento per verificare l'elemento duplicato prima di aggiungere un nuovo elemento.

public void insert(int x){ 
      //effect: Check duplicate elements if not x to the elements; 
       boolean found = false; 
       if(super.size()!=0){ 
        for(int i=0; i<super.size(); i++){ 
         if(super.get(i)==x){ 
          found = true; 
         } 
        } 
       } 
       if(found){ return; } 
       else{ super.add(x); } 
     } 

come posso fare? Grazie.

Inoltre

ecco la mia nomi delle classi InSetExtra

public class IntSetExtra extends ArrayList<Integer> { 


    private static final long serialVersionUID = 1L; 

    public IntSetExtra(){ 
     super(); 
    } 

    public void insert(int x){ 
     //effect: Check duplicate elements if not x to the elements; 
      boolean found = false; 
      if(super.size()!=0){ 
       for(int i=0; i<super.size(); i++){ 
        if(super.get(i)==x){ 
         found = true; 
        } 
       } 
      } 
      if(found){ return; } 
      else{ super.add(x); } 
    } 

    public String toString(){ 
     //effect: return string of this. 
     if(super.size()==0) return "[]"; 
     String s = "[" + super.get(0).toString(); 
     for(int i=1; i<super.size(); i++){ 
      s += ", " + super.get(i).toString(); 
     } 
     return s += "]"; 
    } 

} 

e ho bisogno di inserire una grande dimensione di elementi, ad esempio:

IntSetExtra a, b; 

    a = new IntSetExtra(); 
    b = new IntSetExtra(); 

    for(int i=0; i<30000; i++){ a.insert(2*i); } 
    for(int i=0; i<30000; i++){ a.insert(i); } 

    System.out.println("a sub = "+a.toString().substring(0, 37)); 

cosa devo fare?

ps. il mio istruttore deve utilizzare solo ArrayList

Answer 1

Ecco come lo farei: (spiegazione nei commenti)

public void insert(int x){ 
    // loop through all elements 
    for (int i = 0; i < size(); i++) { 
     // if the element you are looking at is smaller than x, 
     // go to the next element 
     if (get(i) < x) continue; 
     // if the element equals x, return, because we don't add duplicates 
     if (get(i) == x) return; 
     // otherwise, we have found the location to add x 
     add(i, x); 
     return; 
    } 
    // we looked through all of the elements, and they were all 
    // smaller than x, so we add ax to the end of the list 
    add(x); 
} 

La soluzione attuale che hai postato sembra per lo più corretto, tranne per il fatto che non salverà gli elementi in ordine crescente.

Answer 2

Uso TreeSet quando voglio aggiungere elementi non duplicati a un Set. Dagli Un colpo!

Answer 3

Dato che si tratta di compiti a casa, presumo che sia necessario utilizzare uno ArrayList e implementare la logica manualmente (anziché utilizzare TreeSet come soluzione ovvia). Penso che il seguente suggerimento dovrebbe essere sufficiente per finalizzare l'implementazione :-)

Se gli elementi dell'array sono già in ordine crescente, non è necessario eseguire il ciclo dell'intero array. Cerca solo il primo elemento che è uguale o maggiore del nuovo elemento. Se uguale, hai un dupe. Se maggiore, inserisci il nuovo elemento prima di esso e hai finito. Se tutti gli elementi esistenti sono più piccoli di quelli nuovi, inseriscili alla fine.

Ciò fornirà prestazioni O (n) come richiesto. Tuttavia, come miglioramento, puoi prendere in considerazione l'utilizzo di binary search anziché linear.

Answer 4

Perché non utilizzare TreeSet: http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html

Poiché si tratta di domanda compiti e ArrayList devono essere utilizzati Sto cambiando la mia risposta.

Sarà necessario utilizzare la traslazione lineare e confrontare gli elementi. Agire di conseguenza:

• se nuovo elemento è uguale a elemento corrente non fare nulla e restituire.
• se il nuovo elemento è maggiore dell'elemento corrente passa a successivo.
• se nuovo elemento è più piccolo dell'elemento corrente aggiungi elemento a questo indice e restituisce.
• se si raggiunge la fine della lista mentre si attraversa, si aggiunge nuovo elemento e si ritorna. (Questo aggiungerà elemento alla fine della lista)

Presumo qui che tutti gli elementi vengano aggiunti utilizzando l'algoritmo di cui sopra. Quindi ArrayList è sempre ordinato :).

Ecco il codice:

public void insert(int x) { 
    for (int i = 0; i < size(); i++) { 
     if (x == get(i)) { 
      // if new element is equal to current element do nothing and 
      // return 
      return; 
     } else if (x > get(i)) { 
      // if new element is greater than current element traverse to 
      // next. 
      continue; 
     } 
     // code reaches here if new element is smaller than current element 
     // add element at this index and return. 
     add(i, x); 
     return; 
    } 
    // if end of list is reached while traversing then add new element and 
    // return. (This will add element at the end of list) 
    add(x); 
} 

Spero che questo aiuti.

Answer 5

Una lista è una lista e non un insieme e se si comporta come un set, si rompe il suo contratto. Inserimento in un TreeSet dovrebbe essere O (log (n)) o giù di lì ...

Answer 6

Creare una classe per la nuova struttura dati.

Ogni volta che viene aggiunto un valore di dati, eseguire una ricerca binaria sull'array per accertarsi che il valore di dati non sia già presente. Se è già presente, genera un'eccezione. Se non è presente, inseriscilo nella sua posizione ordinata.

Prendere nota dei compiti a casa che esiste una struttura dati esistente (TreeSet) che esegue questa funzionalità, ma lo fa tramite un'implementazione migliore rispetto a quella appena creata.

Answer 7

Ecco un metodo di inserimento in O (n).

public void insert(int x) { 
    int pos = Collections.binarySearch(this, x); 
    if (pos < 0) { 
     add(-pos-1, x); 
    } 
}