wake-up-neo.com

So entfernen Sie Duplikate effizient aus einem Array, ohne Set zu verwenden

Ich wurde gebeten, meine eigene Implementierung zu schreiben, um doppelte Werte in einem Array zu entfernen. Hier ist was ich geschaffen habe. Nach Tests mit 1.000.000 Elementen hat es jedoch sehr lange gedauert. Gibt es etwas, was ich tun kann, um meinen Algorithmus zu verbessern oder Fehler zu entfernen? 

Ich muss meine eigene Implementierung schreiben - nicht um verwende Set , HashSet usw. oder andere Tools wie Iteratoren. Einfach ein Array zum Entfernen von Duplikaten.

public static int[] removeDuplicates(int[] arr) {

    int end = arr.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (arr[i] == arr[j]) {                  
                int shiftLeft = j;
                for (int k = j+1; k < end; k++, shiftLeft++) {
                    arr[shiftLeft] = arr[k];
                }
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }
    return whitelist;
}
35
ashur

Da diese Frage immer noch viel Beachtung findet, habe ich mich entschlossen, diese zu beantworten, indem Sie diese Antwort aus Code Review.SE :

Sie folgen der gleichen Philosophie wie die Blasensortierung. sehr, sehr, sehr langsam. Hast du das probiert ?:

  • Sortieren Sie Ihr ungeordnetes Array mit quicksort . Quicksort ist viel schneller als Bubblesort (ich weiß, Sie sortieren nicht, aber der Algorithmus, dem Sie folgen, ist fast derselbe wie Blasensortierung, um das Array zu durchlaufen). 

  • Beginnen Sie dann mit dem Entfernen von Duplikaten (wiederholte Werte stehen neben jedem anderen ). In einer for-Schleife können Sie zwei Indizes haben: source und destination. (In jeder Schleife kopieren Sie source in destination, es sei denn, sie sind gleich und erhöhen beide um 1). Jedes Mal, wenn Sie eine .__ finden. Duplizieren Sie die Quelle inkrementieren (und führen Sie die Kopie nicht durch) . @morgano

2
ashur

sie können die Hilfe der Sammlung Set verwenden

int end = arr.length;
Set<Integer> set = new HashSet<Integer>();

for(int i = 0; i < end; i++){
  set.add(arr[i]);
}

wenn Sie dieses set jetzt durchlaufen, enthält es nur eindeutige Werte. Iterationscode ist wie folgt:

Iterator it = set.iterator();
while(it.hasNext()) {
  System.out.println(it.next());
}
35
Android Killer

Hinweis: Ich gehe davon aus, dass das Array sortiert ist.

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);

ausgabe:

  1 3 7 8 9 10
14
Kick Buttowski

Da Sie davon ausgehen können, dass der Bereich zwischen 0-1000 liegt, gibt es eine sehr einfache und effiziente Lösung

//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;
}

Dies verläuft in linearer Zeit O (n). Vorsichtsmaßnahme: Das zurückgegebene Array wird sortiert. Wenn dies nicht zulässig ist, ist diese Antwort ungültig.

7
Esailija

Leichte Änderung am ursprünglichen Code selbst, indem die innerste for-Schleife entfernt wird.

public static int[] removeDuplicates(int[] arr){
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (arr[i] == arr[j]) {                  
                /*int shiftLeft = j;
                for (int k = j+1; k < end; k++, shiftLeft++) {
                    arr[shiftLeft] = arr[k];
                }*/
                arr[j] = arr[end-1];
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    /*for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }*/
    System.arraycopy(arr, 0, whitelist, 0, end);
    return whitelist;
}
6
Pavan Kumar
class Demo 
{
    public static void main(String[] args) 
    {
        int a[]={3,2,1,4,2,1};
        System.out.print("Before Sorting:");
        for (int i=0;i<a.length; i++ )
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print ("\nAfter Sorting:");
        //sorting the elements
        for(int i=0;i<a.length;i++)
        {
            for(int j=i;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    int temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

            }
        }

        //After sorting
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print("\nAfter removing duplicates:");
        int b=0;
        a[b]=a[0];
        for(int i=0;i<a.length;i++)
        {
            if (a[b]!=a[i])
            {
                b++;
                a[b]=a[i];
            }
        }
        for (int i=0;i<=b;i++ )
        {
            System.out.print(a[i]+"\t");
        }
    }
}
  OUTPUT:Before Sortng:3 2 1 4 2 1 After Sorting:1 1 2 2 3 4 
                Removing Duplicates:1 2 3 4
6
user3752541

Es gibt viele Lösungen für dieses Problem. 

  1. Der Sortieransatz 

    • Sie sortieren Ihr Array und lösen nur eindeutige Elemente auf 
  2. Der gesetzte Ansatz 

    • Sie deklarieren ein HashSet, in dem Sie alle Elemente ablegen, dann haben Sie nur eindeutige. 
  3. Sie erstellen ein boolesches Array, das die zurückgegebenen Elemente darstellt (dies hängt von Ihren Daten im Array ab). 

Wenn Sie mit großen Datenmengen umgehen, würde ich die 1. Lösung wählen. Da Sie keinen zusätzlichen Speicher zuweisen, ist das Sortieren recht schnell. Für kleine Datenmengen wäre die Komplexität n ^ 2, aber für große i ist n log n.

Was ist, wenn Sie zwei boolsche Arrays erstellen: 1 für negative Werte und 1 für positive Werte und alles auf false setzen.

Anschließend durchlaufen Sie das Eingabe-Array und suchen in den Arrays nach, wenn Sie den Wert bereits ermittelt haben. Wenn dies nicht der Fall ist, fügen Sie ihn dem Ausgabe-Array hinzu und markieren es als bereits verwendet.

4
DaMachk

Dies ist eine einfache Methode zum Sortieren der Elemente im Array

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]);
        }


    }
}
2
package com.pari.practice;

import Java.util.HashSet;
import Java.util.Iterator;

import com.pari.sort.Sort;

public class RemoveDuplicates {

 /**
 * brute force- o(N square)
 * 
 * @param input
 * @return
 */
public static int[] removeDups(int[] input){
    boolean[] isSame = new boolean[input.length];
    int sameNums = 0;

    for( int i = 0; i < input.length; i++ ){
        for( int j = i+1; j < input.length; j++){
            if( input[j] == input[i] ){ //compare same
                isSame[j] = true;
                sameNums++;
            }
        }
    }

    //compact the array into the result.
    int[] result = new int[input.length-sameNums];
    int count = 0;
    for( int i = 0; i < input.length; i++ ){
        if( isSame[i] == true) {
            continue;
        }
        else{
            result[count] = input[i];
            count++;
        }
    }

    return result;
}

/**
 * set - o(N)
 * does not guarantee order of elements returned - set property
 * 
 * @param input
 * @return
 */
public static int[] removeDups1(int[] input){
    HashSet myset = new HashSet();

    for( int i = 0; i < input.length; i++ ){
        myset.add(input[i]);
    }

    //compact the array into the result.
    int[] result = new int[myset.size()];
    Iterator setitr = myset.iterator();
    int count = 0;
    while( setitr.hasNext() ){
        result[count] = (int) setitr.next();
        count++;
    }

return result;
}

/**
 * quicksort - o(Nlogn)
 * 
 * @param input
 * @return
 */
public static int[] removeDups2(int[] input){
    Sort st = new Sort();
    st.quickSort(input, 0, input.length-1); //input is sorted

    //compact the array into the result.
    int[] intermediateResult = new int[input.length];
    int count = 0;
    int prev = Integer.MIN_VALUE;
    for( int i = 0; i < input.length; i++ ){
        if( input[i] != prev ){
            intermediateResult[count] = input[i];
            count++;
        }
        prev = input[i];
    }

    int[] result = new int[count];
    System.arraycopy(intermediateResult, 0, result, 0, count);

    return result;
}


public static void printArray(int[] input){
    for( int i = 0; i < input.length; i++ ){
        System.out.print(input[i] + " ");
    }
}

public static void main(String[] args){
    int[] input = {5,6,8,0,1,2,5,9,11,0};
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups1(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups2(input));
}
}

Ausgabe: 5 6 8 0 1 2 9 11 

0 1 2 5 6 8 9 11 

0 1 2 5 6 8 9 11 

Ich habe gerade den obigen Code zum Ausprobieren geschrieben. Vielen Dank.

2
user3222017
int tempvar=0; //Variable for the final array without any duplicates
     int whilecount=0;    //variable for while loop
     while(whilecount<(nsprtable*2)-1) //nsprtable can be any number
     {
//to check whether the next value is idential in case of sorted array       
if(temparray[whilecount]!=temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+1;
        }
        else if (temparray[whilecount]==temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+2;
        }
     }

Hoffe das hilft oder löst den Zweck.

1
driftking9987
public static int[] removeDuplicates(int[] arr){
    HashSet<Integer> set = new HashSet<>();
    final int len = arr.length;
    //changed end to len
    for(int i = 0; i < len; i++){
        set.add(arr[i]);
    }

    int[] whitelist = new int[set.size()];
    int i = 0;
    for (Iterator<Integer> it = set.iterator(); it.hasNext();) {
        whitelist[i++] = it.next();
    }
    return whitelist;
}

Läuft in O(N) Zeit anstelle Ihrer O (N ^ 3) - Zeit

1
David Xu
public static void main(String args[]) {
    int[] intarray = {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};

    Set<Integer> set = new HashSet<Integer>();
    for(int i : intarray) {
        set.add(i);
    }

    Iterator<Integer> setitr = set.iterator();
    for(int pos=0; pos < intarray.length; pos ++) {
        if(pos < set.size()) {
            intarray[pos] =setitr.next();
        } else {
            intarray[pos]= 0;
        }
    }

    for(int i: intarray)
    System.out.println(i);
}
1
Programmer

Sie müssen Ihr Array sortieren, Duplikate dann wiederholen und entfernen. Da Sie keine anderen Tools verwenden können, müssen Sie selbst Code schreiben.

Sie können Beispiele für das Quicksort in Java im Internet (auf dem dieses Beispiel basiert) leicht finden.

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;
}

Der Prozess läuft also in 3 Schritten ab.

  1. Sortieren Sie das Array - O(nlgn)
  2. Duplikate entfernen - O(n)
  3. Verdichten Sie das Array - O(n)

Dies verbessert also Ihren O(n^3)-Ansatz erheblich.

Ausgabe:

[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]

EDIT

OP-Zustände Werte innerhalb des Arrays spielen keine Rolle. Aber ich kann davon ausgehen, dass der Bereich zwischen 0-1000 liegt. Dies ist ein klassischer Fall, in dem eine O(n) - Sortierung verwendet werden kann.

Wir erstellen ein Array der Größe range +1, in diesem Fall 1001. Wir durchlaufen dann die Daten und erhöhen die Werte in jedem Index, die dem Datenpunkt entsprechen.

Dann können wir das resultierende Array komprimieren und Werte löschen, die nicht inkrementiert wurden. Dadurch werden die Werte eindeutig, da die Zählung ignoriert wird.

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));
}

Ausgabe:

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

Überprüfen Sie für ein sortiertes Array einfach den nächsten Index:

//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;
}
1
mc_fish

Es macht keinen großen Spaß, Benutzereingaben zu aktualisieren, jedoch unter Berücksichtigung Ihrer Einschränkungen ...

public int[] removeDup(int[] nums) {
  Arrays.sort(nums);
  int x = 0;
  for (int i = 0; i < nums.length; i++) {
    if (i == 0 || nums[i] != nums[i - 1]) {
    nums[x++] = nums[i];
    }
  }
  return Arrays.copyOf(nums, x);
}

Die Array-Sortierung kann leicht durch einen beliebigen nlog (n) -Algorithmus ersetzt werden.

1

Ich weiß, das ist irgendwie tot, aber ich habe es nur für meinen eigenen Gebrauch geschrieben. Es ist mehr oder weniger das gleiche wie das Hinzufügen eines Hashsatzes und das anschließende Herausziehen aller Elemente. Es sollte in O(nlogn) im schlimmsten Fall laufen.

    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;
    }
}
1
Eagle

Die effizienteste Methode zum Entfernen von Duplikaten aus einem Integer-Array ohne Verwendung von set besteht darin, ein temporäres Array zu erstellen und das ursprüngliche Array zu iterieren und zu prüfen, ob die Nummer im temporären Array vorhanden ist . Bitte beachten Sie den folgenden Codeausschnitt:

package com.numbers;

import Java.util.Arrays;

public class RemoveDuplicates {
    public int[] removeDuplicate(int[] array) {
        int[] tempArray = new int[array.length];
        int j = 0;
        for (int i : array) {
            if (!isExists(tempArray, i)) {
                tempArray[j++] = i;
            }
        }
        return tempArray;
    }

    public static boolean isExists(int[] array, int num) {
        if (array == null)
            return false;
        for (int i : array) {
            if (i == num) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int [] array = { 10, 20, 30, 10, 45, 30 };
        RemoveDuplicates duplicates = new RemoveDuplicates();
        System.out.println("Before removing duplicates : " + Arrays.toString(array));
        int [] newArray = duplicates.removeDuplicate(array);
        System.out.println("After removing duplicates : " + Arrays.toString(newArray));

    }
}
0
Sudhir Ojha

Wie wäre es mit diesem, nur für sortiertes Array von Zahlen, um ein Array ohne Duplikate zu drucken, ohne Set oder andere Collections zu verwenden, nur Array: 

 public static int[] removeDuplicates(int[] array) {
    int[] nums =new int[array.length];
    int addedNum = 0;
    int j=0;
    for(int i=0;i<array.length;i++) {
        if (addedNum != array[i]) {
        nums[j] = array[i];
        j++;
        addedNum = nums[j-1];
        }
    }
    return Arrays.copyOf(nums, j);
}

Array aus 1040 duplizierten Zahlen, verarbeitet in 33020 Nanosekunden ( 0,033020 Millisekunden ). 

0
pandabear
 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;
}

}

0
Avinash Pande

Nur ein Trick, um Duplikate zu entfernen.

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");
        }
    }

}
0

Warum prüfen nicht alle Leute diese Zeilen?

Ich muss meine eigene Implementierung schreiben - um Set, HashSet usw. nicht zu verwenden. Einfach ein Array zum Entfernen von Duplikaten. 

Ich poste eine sehr einfache Implementierung mit der Pflege der obigen Zeile.

public class RemoveDuplicates {

public static void main(String[] args) {

    int[] arr = { 1, 2, 3, 4, 2, 3, 1 }; // input array
    int len = arr.length;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < len; j++) {
            if (arr[i] == arr[j]) {
                while (j < (len) - 1) {
                    arr[j] = arr[j - 1];
                    j++;
                }
                len--;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        System.out.print("  " +arr[i]);
    }

   }
 }

Eingabe: 1, 2, 3, 4, 2, 3, 1

Ausgabe: 1 2 3 4

0
Ved Prakash
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;
    }
0
venkata harish
public void removeDup(){ 
String[] arr = {"1","1","2","3","3"};
          boolean exists = false;
          String[] arr2 = new String[arr.length];
          int count1 = 0;
          for(int loop=0;loop<arr.length;loop++)
            {
              String val = arr[loop];
              exists = false;
              for(int loop2=0;loop2<arr2.length;loop2++)
              {     
                  if(arr2[loop2]==null)break;
                  if(arr2[loop2]==val){
                        exists = true;
                }
              }
              if(!exists) {
                    arr2[count1] = val;
                    count1++;
              }
            }
}
0
Pradeep
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();
}
0
Falguni

Ich finde die Idee von Android Killer großartig, aber ich habe mich nur gefragt, ob wir HashMap nutzen können. Also habe ich ein kleines Experiment gemacht. Und ich fand, dass HashMap schneller scheint als HashSet.

Hier ist der Code:

    int[] input = new int[1000000];

    for (int i = 0; i < input.length; i++) {
        Random random = new Random();
        input[i] = random.nextInt(200000);
    }

    long startTime1 = new Date().getTime();
    System.out.println("Set start time:" + startTime1);

    Set<Integer> resultSet = new HashSet<Integer>();

    for (int i = 0; i < input.length; i++) {
        resultSet.add(input[i]);
    }

    long endTime1 = new Date().getTime();
    System.out.println("Set end time:"+ endTime1);
    System.out.println("result of set:" + (endTime1 - startTime1));     
    System.out.println("number of Set:" + resultSet.size() + "\n");

    long startTime2 = new Date().getTime();
    System.out.println("Map start time:" + startTime1);

    Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();

    for (int i = 0; i < input.length; i++) {
        if (!resultMap.containsKey(input[i]))
            resultMap.put(input[i], input[i]);
    }

    long endTime2 = new Date().getTime();
    System.out.println("Map end Time:" + endTime2);
    System.out.println("result of Map:" + (endTime2 - startTime2));
    System.out.println("number of Map:" + resultMap.size());

Hier ist das Ergebnis:

Set start time:1441960583837
Set end time:1441960583917
result of set:80
number of Set:198652

Map start time:1441960583837
Map end Time:1441960583983
result of Map:66
number of Map:198652
0
jonathan

Hier ist meine Lösung. Die zeitliche Komplexität ist 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();
    }

Wenn Sie Java 8-Streams verwenden dürfen:

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

Okay, Sie können Set oder andere Sammlungen nicht verwenden. Eine Lösung, die ich hier bisher nicht sehe, ist die Verwendung eines Bloom-Filters , bei dem es sich im Wesentlichen um ein Array von Bits handelt, das möglicherweise Ihre Anforderungen erfüllt.

Der Bloom-Filter ist eine schöne und sehr praktische Technik, die schnell und platzsparend ist. Mit ihr lässt sich schnell überprüfen, ob ein Element in einem Set vorhanden ist, ohne das Set selbst oder die Elemente zu speichern. Es hat eine (normalerweise kleine) falsch positive Rate, aber keine falsch negative Rate. Mit anderen Worten: Wenn ein Bloom-Filter Ihnen mitteilt, dass ein Element bisher noch nicht gesehen wurde, können Sie sicher sein, dass dies nicht der Fall ist. Wenn es jedoch sagt, dass ein Element gesehen wurde, müssen Sie es tatsächlich überprüfen. Dies spart immer noch viel Zeit, wenn nicht zu viele Duplikate in Ihrer Liste enthalten sind (für diese ist keine Schleife erforderlich, außer in der kleinen Wahrscheinlichkeit, dass ein falsch positives Ergebnis vorliegt) - Sie wählen diese Rate normalerweise danach, wie viel Speicherplatz, den Sie dem Bloom-Filter zuweisen möchten (Faustregel: weniger als 10 Bits pro eindeutigem Element für eine falsch positive Rate von 1%).

Es gibt viele Implementierungen von Bloom-Filtern, siehe z. hier oder hier , deshalb werde ich das in dieser Antwort nicht wiederholen. Nehmen wir einfach an, das in dieser letzten Referenz beschriebene api, insbesondere die description von put(E e):

true, wenn sich die Bits des Bloom-Filters als Ergebnis dieser Operation geändert haben. Wenn sich die Bits geändert haben, ist dies definitiv, wenn das Objekt zum ersten Mal zum Filter hinzugefügt wurde. Wenn sich die Bits nicht geändert haben, ist möglicherweise das erste Objekt, das dem Filter hinzugefügt wurde. (...)

Eine Implementierung mit einem solchen Bloom-Filter wäre dann:

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();
}

Wenn Sie das eingehende Array an Ort und Stelle ändern können, ist natürlich keine ArrayList erforderlich: Wenn Sie am Ende die tatsächliche Anzahl der eindeutigen Elemente kennen, brauchen Sie nur die Funktion arraycopy() zu kennen.

0
Pierre D

Dies verwendet nicht Set, Map, List oder eine zusätzliche Sammlung, sondern nur zwei Arrays:

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;
    }

}

Und vor allem, um es zu testen

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"));
    }

}

Und die Ausgabe:

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
0
Juan Furattini

Dies ist eine einfachere und bessere Möglichkeit, stattdessen Arraylisten zu verwenden:

public static final <T> ArrayList<T> removeDuplicates(ArrayList<T> in){
    ArrayList<T> out = new ArrayList<T>();
    for(T t : in) 
        if(!out.contains(t)) 
            out.add(t);
    return out;
}
0
Jeremiah

Dies ist eine Interviewfrage: Entfernen Sie Duplikate aus einem Array. Ich darf keine Sets oder Sammlungen verwenden. Die Komplettlösung ist:

public class Test4 {
public static void main(String[] args) {
     int a[] = {1, 2, 2, 3, 3, 3, 6,6,6,6,6,66,7,65}; 
              int newlength =    lengthofarraywithoutduplicates(a);
              for(int i = 0 ; i < newlength ;i++) {
                  System.out.println(a[i]);
              }//for
}//main

private static int lengthofarraywithoutduplicates(int[] a) {
     int count = 1 ;
     for (int i = 1; i < a.length; i++) {
          int ch = a[i];
          if(ch != a[i-1]) {
              a[count++] = ch;
          }//if
    }//for
    return count;

}//fix

}//end1
0
Soudipta Dutta