Façon la plus efficace de supprimer les doublons d'un tableau sans l'aide de Jeu

Note: je suis en supposant que le tableau est trié.

Code:

int[] input = new int[]{1, 1, 3, 7, 7, 8, 9, 9, 9, 10};
int current = input[0];
boolean found = false;

for (int i = 0; i < input.length; i++) {
    if (current == input[i] && !found) {
        found = true;
    } else if (current != input[i]) {
        System.out.print(" " + current);
        current = input[i];
        found = false;
    }
}
System.out.print(" " + current);

de sortie:

  1 3 7 8 9 10

Puisque vous pouvez assumer la gamme est entre 0-1000 il y a une solution très simple et efficace

//Throws an exception if values are not in the range of 0-1000
public static int[] removeDuplicates(int[] arr) {
    boolean[] set = new boolean[1001]; //values must default to false
    int totalItems = 0;

    for (int i = 0; i < arr.length; ++i) {
        if (!set[arr[i]]) {
            set[arr[i]] = true;
            totalItems++;
        }
    }

    int[] ret = new int[totalItems];
    int c = 0;
    for (int i = 0; i < set.length; ++i) {
        if (set[i]) {
            ret[c++] = i;
        }
    }
    return ret;
}

Cela s'exécute en temps linéaire O(n). Mise en garde: le tableau retourné est trié donc, si c'est illégal alors cette réponse n'est pas valide.

Il existe de nombreuses solution de ce problème.

1. Le tri approche

   • Vous sorte de votre tableau et résoudre seulement unique articles

2. L'approche

   • Vous déclarez un HashSet où vous mettez tous les articles, alors vous avez seulement unique proches.

3. Vous créer un booléen tableau qui représentent les éléments de tous les prêts retourné, (cela dépend de vos données dans le tableau).

Si vous faites affaire avec une grande quantité de données, je choisirais le 1. solution. Comme vous n'avez pas à allouer de la mémoire supplémentaire et que le tri est assez rapide. Pour petit ensemble de données de la complexité serait n^2, mais pour les grands, je n log n.

C'est simple pour trier les éléments dans le tableau

public class DublicatesRemove {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter size of the array");
int l = Integer.parseInt(br.readLine());
int[] a = new int[l];
//insert elements in the array logic
for (int i = 0; i < l; i++) 
{
System.out.println("enter a element");
int el = Integer.parseInt(br.readLine());
a[i] = el;
}
//sorting elements in the array logic
for (int i = 0; i < l; i++) 
{
for (int j = 0; j < l - 1; j++) 
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
//remove duplicate elements logic
int b = 0;
a[b] = a[0];
for (int i = 1; i < l; i++)
{
if (a[b] != a[i])
{
b++;
a[b]=a[i];
}
}
for(int i=0;i<=b;i++)
{
System.out.println(a[i]);
}
}
}

Depuis que cette question est encore l'objet de beaucoup d'attention, j'ai décidé de répondre par la copie cette réponse de la Révision du Code.SE:

Vous êtes suivant la même philosophie que le tri à bulles, qui est
très, très, très lent. Avez-vous essayé ceci?:

• Trier vos non ordonnée tableau avec quicksort. Quicksort est beaucoup plus rapide
  que le tri à bulles (je sais, vous n'êtes pas le tri, mais l'algorithme de vous
  suivre est presque le même que le tri à bulles pour parcourir le tableau).

• Puis commencer à supprimer les doublons (les valeurs répétées sera à côté de chaque
  d'autres). Dans un for boucle vous pourriez avoir deux indices: source et
  destination. (Sur chaque boucle vous copiez source à destination à moins qu'ils
  sont les mêmes, et d'un incrément à la fois par 1). Chaque fois que vous trouver un
  duplicata vous incrément de source (et de ne pas effectuer la copie).
  @morgano

Vous avez besoin de trier votre tableau puis ensuite en boucle et supprimer les doublons. Comme vous ne pouvez pas utiliser d'autres outils que vous devez écrire le code sera vous-même.

Vous pouvez facilement trouver des exemples de quicksort en Java sur internet (sur lequel cet exemple est basé).

public static void main(String[] args) throws Exception {
final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1};
System.out.println(Arrays.toString(original));
quicksort(original);
System.out.println(Arrays.toString(original));
final int[] unqiue = new int[original.length];
int prev = original[0];
unqiue[0] = prev;
int count = 1;
for (int i = 1; i < original.length; ++i) {
if (original[i] != prev) {
unqiue[count++] = original[i];
}
prev = original[i];
}
System.out.println(Arrays.toString(unqiue));
final int[] compressed = new int[count];
System.arraycopy(unqiue, 0, compressed, 0, count);
System.out.println(Arrays.toString(compressed));
}
private static void quicksort(final int[] values) {
if (values.length == 0) {
return;
}
quicksort(values, 0, values.length - 1);
}
private static void quicksort(final int[] values, final int low, final int high) {
int i = low, j = high;
int pivot = values[low + (high - low) / 2];
while (i <= j) {
while (values[i] < pivot) {
i++;
}
while (values[j] > pivot) {
j--;
}
if (i <= j) {
swap(values, i, j);
i++;
j--;
}
}
if (low < j) {
quicksort(values, low, j);
}
if (i < high) {
quicksort(values, i, high);
}
}
private static void swap(final int[] values, final int i, final int j) {
final int temp = values[i];
values[i] = values[j];
values[j] = temp;
}

De sorte que le processus s'exécute en 3 étapes.

1. Trier le tableau - O(nlgn)
2. Supprimer les doublons - O(n)
3. Compact le tableau - O(n)

Donc, ce qui améliore de manière significative sur votre O(n^3) approche.

De sortie:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1]
[1, 1, 1, 2, 4, 4, 7, 8, 8, 9, 9]
[1, 2, 4, 7, 8, 9, 0, 0, 0, 0, 0]
[1, 2, 4, 7, 8, 9]

MODIFIER

OP états des valeurs à l'intérieur de la matrice de n'importe pas vraiment. Mais je peux supposer que la fourchette est entre 0-1000. C'est un cas classique où un O(n) peut être utilisé.

Nous créons un tableau de taille range +1, dans ce cas 1001. Nous avons ensuite une boucle sur les données et incrémenter les valeurs de chaque indice correspondant à la datapoint.

Nous pouvons alors compact le tableau qui en résulte, à l'abandon des valeurs de la n'ont pas été incrémenté. Cela rend les valeurs uniques que nous ignorons le nombre de.

public static void main(String[] args) throws Exception {
final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000};
System.out.println(Arrays.toString(original));
final int[] buckets = new int[1001];
for (final int i : original) {
buckets[i]++;
}
final int[] unique = new int[original.length];
int count = 0;
for (int i = 0; i < buckets.length; ++i) {
if (buckets[i] > 0) {
unique[count++] = i;
}
}
final int[] compressed = new int[count];
System.arraycopy(unique, 0, compressed, 0, count);
System.out.println(Arrays.toString(compressed));
}

De sortie:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000]
[1, 2, 4, 7, 8, 9, 1000]

Je sais que c'est un peu mort, mais je viens d'écrire pour mon propre usage. C'est plus ou moins le même que l'ajout d'un hashset, puis en tirant tous les éléments en dehors de ça. Il doit s'exécuter en O(nlogn) le pire des cas.

    public static int[] removeDuplicates(int[] numbers) {
Entry[] entries = new Entry[numbers.length];
int size = 0;
for (int i = 0 ; i < numbers.length ; i++) {
int nextVal = numbers[i];
int index = nextVal % entries.length;
Entry e = entries[index];
if (e == null) {
entries[index] = new Entry(nextVal);
size++;
} else {
if(e.insert(nextVal)) {
size++;
}
}
}
int[] result = new int[size];
int index = 0;
for (int i = 0 ; i < entries.length ; i++) {
Entry current = entries[i];
while (current != null) {
result[i++] = current.value;
current = current.next;
}
}
return result;
}
public static class Entry {
int value;
Entry next;
Entry(int value) {
this.value = value;
}
public boolean insert(int newVal) {
Entry current = this;
Entry prev = null;
while (current != null) {
if (current.value == newVal) {
return false;
} else if(current.next != null) {
prev = current;
current = next;
}
}
prev.next = new Entry(value);
return true;
}
}

Pour un Tableau trié, il suffit de voir le prochain indice:

//sorted data!
public static int[] distinct(int[] arr) {
int[] temp = new int[arr.length];
int count = 0;
for (int i = 0; i < arr.length; i++) {
int current = arr[i];
if(count > 0 )
if(temp[count - 1] == current)
continue;
temp[count] = current;
count++;
}
int[] whitelist = new int[count];
System.arraycopy(temp, 0, whitelist, 0, count);
return whitelist;
}

public static void main(String[] args) {
Integer[] intArray = { 1, 1, 1, 2, 4, 2, 3, 5, 3, 6, 7, 3, 4, 5 };
Integer[] finalArray = removeDuplicates(intArray);
System.err.println(Arrays.asList(finalArray));
}
private static Integer[] removeDuplicates(Integer[] intArray) {
int count = 0;
Integer[] interimArray = new Integer[intArray.length];
for (int i = 0; i < intArray.length; i++) {
boolean exists = false;
for (int j = 0; j < interimArray.length; j++) {
if (interimArray[j]!=null && interimArray[j] == intArray[i]) {
exists = true;
}
}
if (!exists) {
interimArray[count] = intArray[i];
count++;
}
}
final Integer[] finalArray = new Integer[count];
System.arraycopy(interimArray, 0, finalArray, 0, count);
return finalArray;
}

Ce n'est pas à l'aide de Jeu, Carte, Liste ou de toute collecte supplémentaire, seulement deux tableaux:

package arrays.duplicates;
import java.lang.reflect.Array;
import java.util.Arrays;
public class ArrayDuplicatesRemover<T> {
public static <T> T[] removeDuplicates(T[] input, Class<T> clazz) {
T[] output = (T[]) Array.newInstance(clazz, 0);
for (T t : input) {
if (!inArray(t, output)) {
output = Arrays.copyOf(output, output.length + 1);
output[output.length - 1] = t;
}
}
return output;
}
private static <T> boolean inArray(T search, T[] array) {
for (T element : array) {
if (element.equals(search)) {
return true;
}
}
return false;
}
}

Et la main pour le tester

package arrays.duplicates;
import java.util.Arrays;
public class TestArrayDuplicates {
public static void main(String[] args) {
Integer[] array = {1, 1, 2, 2, 3, 3, 3, 3, 4};
testArrayDuplicatesRemover(array);
}
private static void testArrayDuplicatesRemover(Integer[] array) {
final Integer[] expectedResult = {1, 2, 3, 4};
Integer[] arrayWithoutDuplicates = ArrayDuplicatesRemover.removeDuplicates(array, Integer.class);
System.out.println("Array without duplicates is supposed to be: " + Arrays.toString(expectedResult));
System.out.println("Array without duplicates currently is: " + Arrays.toString(arrayWithoutDuplicates));
System.out.println("Is test passed ok?: " + (Arrays.equals(arrayWithoutDuplicates, expectedResult) ? "YES" : "NO"));
}
}

Et la sortie:

Array without duplicates is supposed to be: [1, 2, 3, 4]
Array without duplicates currently is: [1, 2, 3, 4]
Is test passed ok?: YES

D'accord, alors vous ne pouvez pas utiliser Set ou d'autres collections. Une seule solution, je ne vois pas ici la mesure est basé sur l'utilisation d'un Filtre de Bloom, qui est essentiellement un tableau de bits, donc peut-être qui répond à vos exigences.

Le filtre de Bloom est une belle et très pratique technique, rapide et efficace, qui peut être utilisé pour faire une vérification rapide de l'existence d'un élément dans un ensemble sans stocker l'ensemble lui-même ou les éléments. Il a un (généralement de petite taille) taux de faux positifs, mais pas de taux de faux négatifs. En d'autres termes, pour votre question, si un filtre de Bloom vous dit qu'un élément n'a pas été vu jusqu'à présent, vous pouvez être sûr qu'il n'a pas. Mais si on dit qu'un élément a été vu, vous avez vraiment besoin de vérifier. Encore permet d'économiser beaucoup de temps si il n'y a pas trop de doublons dans votre liste (pour ceux-ci, il n'y a pas de boucle à faire, sauf dans les petits probabilité cas de faux positif-vous généralement choisi ce taux en fonction de la quantité d'espace que vous êtes prêt à donner à la Floraison de filtre (règle de base: moins de 10 bits par élément unique pour un taux de faux positif de 1%).

Il existe de nombreuses implémentations de filtres de Bloom, voir, par exemple, ici ou ici, donc je ne vais pas répéter ce que, dans cette réponse. Contentons-nous d'assumer l'api décrite dans cette dernière référence, en particulier, la description de put(E e):

true si la Floraison du filtre bits changé à la suite de cette opération. Si les bits changé, c'est certainement la première fois que l'objet a été ajouté au filtre. Si les bits n'ont pas changé, ce pourrait être la première fois que l'objet a été ajouté au filtre. (...)

Une mise en œuvre en utilisant par exemple un filtre de Bloom serait alors:

public static int[] removeDuplicates(int[] arr) {
ArrayList<Integer> out = new ArrayList<>();
int n = arr.length;
BloomFilter<Integer> bf = new BloomFilter<>(...);  //decide how many bits and how many hash functions to use (compromise between space and false positive rate)
for (int e : arr) {
boolean might_contain = !bf.put(e);
boolean found = false;
if (might_contain) {
//check if false positive
for (int u : out) {
if (u == e) {
found = true;
break;
}
}
}
if (!found) {
out.add(e);
}
}
return out.stream().mapToInt(i -> i).toArray();
}

Évidemment, si vous pouvez modifier les entrants réseau en place, il n'est pas nécessaire pour une ArrayList: à la fin, quand tu sais le nombre réel d'éléments uniques, juste arraycopy() ceux.

Voici ma solution. Le temps de la complexité est o(n^2)

public String removeDuplicates(char[] arr) {
StringBuilder sb = new StringBuilder();
if (arr == null)
return null;
int len = arr.length;
if (arr.length < 2)
return sb.append(arr[0]).toString();
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (arr[i] == arr[j]) {
arr[j] = 0;
}
}
if (arr[i] != 0)
sb.append(arr[i]);
}
return sb.toString().trim();
}

 package javaa;
public class UniqueElementinAnArray 
{
public static void main(String[] args) 
{
int[] a = {10,10,10,10,10,100};
int[] output = new int[a.length];
int count = 0;
int num = 0;
//Iterate over an array
for(int i=0; i<a.length; i++)
{
num=a[i];
boolean flag = check(output,num);
if(flag==false)
{
output[count]=num;
++count;
}
}
//print the all the elements from an array except zero's (0)
for (int i : output) 
{
if(i!=0 )
System.out.print(i+"  ");
}
}
/***
* If a next number from an array is already exists in unique array then return true else false
* @param arr   Unique number array. Initially this array is an empty.
* @param num   Number to be search in unique array. Whether it is duplicate or unique.
* @return  true: If a number is already exists in an array else false 
*/
public static boolean check(int[] arr, int num)
{
boolean flag = false;
for(int i=0;i<arr.length; i++)
{
if(arr[i]==num)
{
flag = true;
break;
}
}
return flag;
}

}

public static int[] removeDuplicates(int[] arr) {
int end = arr.length;
HashSet<Integer> set = new HashSet<Integer>(end);
for(int i = 0 ; i < end ; i++){
set.add(arr[i]);
}
return set.toArray();
}

Si vous êtes autorisé à utiliser Java 8 flux:

Arrays.stream(arr).distinct().toArray();

Juste un truc pour supprimer les doublons.

public class RemoveDuplicates {
public static void main(String[] args) {
int[] arr = {2,2,2,2,2,5,9, 4,5,6,1,6,6,2,4,7};
arr = removeDuplicates(arr);    
print(arr);
}
public static int[] removeDuplicates(int [] arr) {
final int garbage = -2147483648;
int duplicates = 0;
for(int i=0; i<arr.length; i++) {
for(int j=i+1; j<arr.length; j++) {
if (arr[i] == arr[j]) {
arr[i] = garbage;
duplicates++;
}
}
}
int[] nArr = new int[arr.length - duplicates];
int nItr = 0;
for(int i=0; i<arr.length; i++) {
if (arr[i] != garbage) {
nArr[nItr] = arr[i];
nItr++;
} 
}
return nArr;
}
public static void print(int [] arr) {
for (int n : arr) {
System.out.print(n + "\t");
}
}
}

public class RemoveDuplicates {
public Integer[] returnUniqueNumbers(Integer[] original,
Integer[] uniqueNumbers) {
int k = 0;  
for (int j =  original.length - 1; j >= 0; j--) {
boolean present = false;
for (Integer u : uniqueNumbers) {
if (u != null){
if(u.equals(original[j])) {
present = true;
}}
}
if (present == false) {
uniqueNumbers[k] = original[j];
k++;
}
}
return uniqueNumbers;
}
public static void main(String args[]) {
RemoveDuplicates removeDup = new RemoveDuplicates();
Integer[] original = { 10, 20, 40, 30, 50, 40, 30, 20, 10, 50, 50, 50,20,30,10,40 };
Integer[] finalValue = new Integer[original.length + 1];
//method to return unique values
Integer[] unique = removeDup.returnUniqueNumbers(original, finalValue);
//iterate to return unique values
for (Integer u : unique) {
if (u != null) {
System.out.println("unique value : " + u);
}
}
}}

Ce code gère les ménagères de tableau contenant plusieurs doubles pour la même valeur et le rendement des éléments uniques.