Éviter les entiers en double dans un tableau d'entiers

Question

Comment éviter que des entiers en double soient ajoutés dans un tableau d'entiers sans utiliser l'une des collections, à savoir Arraylist ou Set etc.?

Answer 1

Si votre problème est de retourner un Integer[], et aucune autre collection, vous pouvez cependant utiliser un Set<Integer>private ment pour éviter les valeurs dupliquées, puis revenez Set<Integer>.toArray(new Integer[0]).

C'est la façon la plus simple à mon humble avis ...

Par exemple:

private Set<Integer> intSet = new HashSet<Integer>(); 

public void setIntArray(Integer[] i){ 
    intSet = new HashSet<Integer>(Arrays.asList(i)); 
} 

public Integer[] getIntArray(){ 
    return intSet.toArray(new Integer[0]); 
} 

Answer 2

sans utiliser aucune des collections, c'est-à-dire Arraylist ou Set etc.?

juste vérifier par tableau avant l'insertion,

vous pouvez utiliser insertion sort et faire le binarysearch il serait peu plus vite

Answer 3

1. Ecrivez une méthode qui ajoute la valeur au tableau.
2. Avant d'ajouter, scannez le tableau si la valeur existe.
3. Sautez l'addition si elle existe.
4. Utilisez seulement cette méthode pour ajouter des valeurs au tableau.
5. Idéalement regrouper le tableau et la méthode dans une classe. Voila: encapsulation!

Answer 4

Vous pouvez créer un autre tableau, nous allons l'appeler exists, de type booléen. Ensuite, chaque fois que vous ajoutez un entier à votre liste principale, vérifiez si exists[newNumber]. Si la valeur est true, elle existe déjà, sinon ajoutez le nombre au tableau entier et définissez la valeur booléenne sur true.

Cette solution fonctionne bien si la plage de nombres a une petite limite. Notez, mon exemple suppose également que l'entier est positif. Une optimisation consiste à utiliser un tableau long [] et à utiliser chaque bit comme indicateur.

Answer 5

Tout d'abord, supposons que le tableau est un tampon et dispose d'espace supplémentaire. Il suffit de faire une boucle pour vérifier chaque valeur. Comme tel

for(int i=0; i<endpointer &&i < buffer.length ; i++){ 
     if(buffer[i]==valueToPutInArray){ 
      valueExists=true; 
      break; 
     } 
    } 
    if(!valueExists) { 
     buffer[endpointer++]=valueToPutInArray; 

    } 

Si le tableau est doit être réaffecté alors vous devez faire quelque chose comme ceci:

int i=0; 
    Integer[] outputArray = new Integer[buffer.length+1]; 
    for(Integer value : buffer) { 
     if(value==valueToPutInArray){ 
      valueExists=true; 
      break; 
     } 
     outputArray[i++]=value; 
    } 
    if(!valueExists) { 
     outputArray[i]=valueToPutInArray; 

    } 

Answer 6

Je vous suggère d'abord vous effectuez Arrays.sort (int []). Utilisez ensuite Arrays.binarySearch (int [], int) pour vérifier si l'élément existe ou non.

Selon javadoc:

/** 
* Sorts the specified array of ints into ascending numerical order. 
* The sorting algorithm is a tuned quicksort, adapted from Jon 
* L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", 
* Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 
* 1993). This algorithm offers n*log(n) performance on many data sets 
* that cause other quicksorts to degrade to quadratic performance. 
* 
* @param a the array to be sorted 
*/ 
public static void sort(int[] a) { 
sort1(a, 0, a.length); 
} 

et BinarySearch:

/** 
* Searches the specified array of ints for the specified value using the 
* binary search algorithm. The array must be sorted (as 
* by the {@link #sort(int[])} method) prior to making this call. If it 
* is not sorted, the results are undefined. If the array contains 
* multiple elements with the specified value, there is no guarantee which 
* one will be found. 
* 
* @param a the array to be searched 
* @param key the value to be searched for 
* @return index of the search key, if it is contained in the array; 
*   otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 
*   <i>insertion point</i> is defined as the point at which the 
*   key would be inserted into the array: the index of the first 
*   element greater than the key, or <tt>a.length</tt> if all 
*   elements in the array are less than the specified key. Note 
*   that this guarantees that the return value will be &gt;= 0 if 
*   and only if the key is found. 
*/ 
public static int binarySearch(int[] a, int key) { 
return binarySearch0(a, 0, a.length, key); 
} 

Et on vous savez si l'élément existe ou non, le repos est facile pour vous.

Answer 7

La solution dépend de vos besoins. Si vous avez une petite taille du tableau (n < 10^6), balayage à travers le réseau à chaque insertion suffirait, mais si vous avez un grand tableau et insertions fréquentes, je propose une autre solution.

La numérisation d'un tableau à chaque insertion nécessiterait une complexité de O (n). Pour les petits nombres, l'overhead est ignorable, mais à mesure que la taille du tableau augmente, la traversée à chaque insertion est inefficace.

Si vous avez besoin de performances et si la mémoire n'est pas votre contrainte, vous pouvez prendre un tableau booléen et initialiser tous les éléments à false. Ensuite, chaque fois que vous obtenez un numéro, assurez-vous de sa valeur d'index dans le tableau booléen à vrai, et lors de l'insertion, vérifiez si la valeur booléenne au numéro d'index de l'élément inséré.

Voici le code pour initialiser le tableau booléen (initialisation cela rendrait tous les éléments faux):

boolean [] duplicateValuesArray = new boolean[Integer.MAX_VALUE]; 

est la fonction ici qui insère un élément dans le tableau:

public void insertElement(int elementToBeInserted) { 
     if(!duplicateValuesArray[elementToBeInserted]) //check if element already in array 
      duplicateValuesArray[elementToBeInserted] = true; 
      mainArray[index++] = elementToBeInserted; 
    } 

Dans de cette façon, chaque fois que vous obtenez un numéro, la valeur de cet indice dans le tableau booléen est réglé sur vrai, et pendant l'insertion, à chaque fois est vérifié l'indice, si la valeur est vrai, cet élément existe dans le tableau, ne l'insérez pas.

La complexité de c'est beaucoup plus faible si vous avez un grand mainArray(n> 10^6) et vous avez des insertions fréquentes. C'est parce que, l'initialisation d'un tableau booléen est une fois O (n) complexité, et après cela, la vérification de l'élément dans le tableau booléen et l'insertion de l'élément est O (1) opération, arrive à temps constant.

complexité Ainsi efficace est réduite à seulement initialiser le tableau booléen. Et même en termes d'empreinte mémoire, cela ne me dérangerait pas car un primitif booléen occupe juste un bit dans la mémoire.

P.S: Fondamentalement, il est une mémoire vs le commerce de performances hors, ce qui est le commerce Computing Universal off, trouve partout.