Rimozione di duplicati da una stringa in Java

Sto cercando di scorrere una stringa per rimuovere i caratteri duplicati.

Ad esempio la stringa aabbccdef dovrebbe diventare abcdef e la stringa abcdabcd dovrebbe diventare abcd

Ecco cosa ho finora:

 public class test { public static void main(String[] args) { String input = new String("abbc"); String output = new String(); for (int i = 0; i < input.length(); i++) { for (int j = 0; j < output.length(); j++) { if (input.charAt(i) != output.charAt(j)) { output = output + input.charAt(i); } } } System.out.println(output); } } 

Qual è il modo migliore per farlo?

Converti la stringa in un array di caratteri e memorizzali in un object LinkedHashSet . Ciò manterrà il tuo ordine e rimuoverà i duplicati. Qualcosa di simile a:

 String string = "aabbccdefatafaz"; char[] chars = string.toCharArray(); Set charSet = new LinkedHashSet(); for (char c : chars) { charSet.add(c); } StringBuilder sb = new StringBuilder(); for (Character character : charSet) { sb.append(character); } System.out.println(sb.toString()); 

Vorrei usare l’aiuto di LinkedHashSet . Rimuove i duplicati (dato che stiamo usando un Set, mantiene l’ordine dato che stiamo utilizzando un elenco di collegamenti collegato). Questa è una specie di soluzione sporca. potrebbe esserci anche un modo migliore.

 String s="aabbccdef"; Set set=new LinkedHashSet(); for(char c:s.toCharArray()) { set.add(Character.valueOf(c)); } 

Prova questa semplice soluzione:

 public String removeDuplicates(String input){ String result = ""; for (int i = 0; i < input.length(); i++) { if(!result.contains(String.valueOf(input.charAt(i)))) { result += String.valueOf(input.charAt(i)); } } return result; } 

Creare uno StringWriter. Esegui la stringa originale usando charAt (i) in un ciclo for. Mantenere una variabile di tipo char mantenendo l’ultimo valore charAt. Se si itera e il valore charAt è uguale a ciò che è memorizzato in quella variabile, non aggiungere a StringWriter. Infine, usa il metodo StringWriter.toString (), ottieni una stringa e fai ciò che ti serve.

L’uso di Stream rende facile.

 import java.util.Arrays; import java.util.stream.Collectors; public class MyClass { public static String removeDuplicates(String myString) { return Arrays.asList(myString.split("")).stream().distinct().collect(Collectors.joining()); } } 

Ecco qualche altra documentazione su Stream e tutto ciò che puoi fare con esso: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

La parte “descrizione” è molto istruttiva sui vantaggi degli Stream.

  String input = "AAAB"; String output = ""; for (int index = 0; index < input.length(); index++) { if (input.charAt(index % input.length()) != input .charAt((index + 1) % input.length())) { output += input.charAt(index); } } System.out.println(output); 

ma non puoi usarlo se l'input ha gli stessi elementi, o se è vuoto!

Codice per rimuovere i caratteri duplicati in una stringa senza utilizzare alcun buffer aggiuntivo. NOTA: una o due variabili aggiuntive vanno bene. Un array extra non è:

 import java.util.*; public class Main{ public static char[] removeDupes(char[] arr){ if (arr == null || arr.length < 2) return arr; int len = arr.length; int tail = 1; for(int x = 1; x < len; x++){ int y; for(y = 0; y < tail; y++){ if (arr[x] == arr[y]) break; } if (y == tail){ arr[tail] = arr[x]; tail++; } } return Arrays.copyOfRange(arr, 0, tail); } public static char[] bigArr(int len){ char[] arr = new char[len]; Random r = new Random(); String alphabet = "[email protected]#$%^&*()-=_+[]{}|;:',.<>/?`~"; for(int x = 0; x < len; x++){ arr[x] = alphabet.charAt(r.nextInt(alphabet.length())); } return arr; } public static void main(String args[]){ String result = new String(removeDupes(new char[]{'a', 'b', 'c', 'd', 'a'})); assert "abcd".equals(result) : "abcda should return abcd but it returns: " + result; result = new String(removeDupes(new char[]{'a', 'a', 'a', 'a'})); assert "a".equals(result) : "aaaa should return a but it returns: " + result; result = new String(removeDupes(new char[]{'a', 'b', 'c', 'a'})); assert "abc".equals(result) : "abca should return abc but it returns: " + result; result = new String(removeDupes(new char[]{'a', 'a', 'b', 'b'})); assert "ab".equals(result) : "aabb should return ab but it returns: " + result; result = new String(removeDupes(new char[]{'a'})); assert "a".equals(result) : "a should return a but it returns: " + result; result = new String(removeDupes(new char[]{'a', 'b', 'b', 'a'})); assert "ab".equals(result) : "abba should return ab but it returns: " + result; char[] arr = bigArr(5000000); long startTime = System.nanoTime(); System.out.println("2: " + new String(removeDupes(arr))); long endTime = System.nanoTime(); long duration = (endTime - startTime); System.out.println("Program took: " + duration + " nanoseconds"); System.out.println("Program took: " + duration/1000000000 + " seconds"); } } 

Come leggere e parlare del codice sopra:

  1. Il metodo chiamato removeDupes utilizza una matrice di caratteri primitivi chiamata arr.
  2. arr è restituito come una matrice di caratteri primitivi "in base al valore". L'arr inol passato è spazzatura raccolta alla fine del metodo membro Main removeDupes.
  3. La complessità di runtime di questo algoritmo è O (n) o più specificamente O (n + (piccola costante)) essendo la costante i caratteri univoci nell'intera matrice di caratteri primitivi.
  4. CopyOfRange non aumenta in modo significativo la complessità del runtime poiché copia solo un numero costante di elementi. L'array di caratteri chiamato arr non è avanzato fino in fondo.
  5. Se si passa null in removeDupes, il metodo restituisce null.
  6. Se si passa una matrice vuota di caratteri primitivi o una matrice contenente un valore, viene restituita una matrice non modificata.
  7. Il metodo removeDupes procede il più velocemente ansible fisicamente, utilizzando completamente la cache L1 e L2, quindi i reindirizzamenti delle filiali sono ridotti al minimo .
  8. Un computer senza problemi con problemi standard del 2015 dovrebbe essere in grado di completare questo metodo con un array di caratteri primitivi contenente 500 milioni di caratteri tra 15 e 25 secondi.

Spiega come funziona questo codice:

La prima parte dell'array passato viene utilizzata come repository per i caratteri univoci che vengono infine restituiti. All'inizio della funzione la risposta è: "i caratteri tra 0 e 1" come tra 0 e coda.

Definiamo la variabile y al di fuori del ciclo perché vogliamo trovare la prima posizione in cui l'indice dell'array che stiamo guardando è stato duplicato nel nostro repository. Quando viene trovato un duplicato, si interrompe e si chiude, y == tail restituisce false e il repository non viene fornito.

quando l'indice x che stiamo sbirciando non è rappresentato nel nostro repository, allora lo estraiamo e lo aggiungiamo alla fine del nostro repository a index code e incrementiamo tail.

Alla fine, restituiamo l'array tra i punti 0 e tail, che dovrebbe essere più piccolo o uguale alla lunghezza dell'array originale.

Esercizio di punti di discussione per interviste con i coder:

Il programma si comporterà diversamente se cambi lo y ++ in ++ y? Perché o perché no.

La copia dell'array alla fine rappresenta un altro passaggio "N" attraverso l'intero array rendendo la complessità di runtime O (n * n) invece di O (n)? Perché o perché no.

Puoi sostituire i doppi uguali confrontando i caratteri primitivi con un .equals? Perché o perché no?

Questo metodo può essere modificato per fare le sostituzioni "per riferimento" anziché come ora "in base al valore"? Perché o perché no?

È ansible aumentare l'efficienza di questo algoritmo ordinando il repository di valori univoci all'inizio di 'arr'? In quali circostanze sarebbe più efficiente?

 public class RemoveRepeated4rmString { public static void main(String[] args) { String s = "harikrishna"; String s2 = ""; for (int i = 0; i < s.length(); i++) { Boolean found = false; for (int j = 0; j < s2.length(); j++) { if (s.charAt(i) == s2.charAt(j)) { found = true; break; //don't need to iterate further } } if (found == false) { s2 = s2.concat(String.valueOf(s.charAt(i))); } } System.out.println(s2); } } 

Ecco un miglioramento della risposta di Dave .

Utilizza HashSet posto del LinkedHashSet leggermente più costoso e riutilizza il buffer chars per il risultato, eliminando la necessità di un StringBuilder .

 String string = "aabbccdefatafaz"; char[] chars = string.toCharArray(); Set present = new HashSet<>(); int len = 0; for (char c : chars) if (present.add(c)) chars[len++] = c; System.out.println(new String(chars, 0, len)); // abcdeftz 

A me sembra che tutti stiano cercando troppo difficile per portare a termine questo compito. Tutto ciò di cui ci preoccupiamo è che copia 1 copia di ogni lettera se si ripete. Quindi, poiché siamo preoccupati solo se questi personaggi si ripetono uno dopo l’altro, i loop nidificati diventano arbitrari, poiché puoi semplicemente confrontare la posizione n con la posizione n + 1. Quindi perché questo copia solo le cose quando sono diverse, per risolvere il problema l’ultimo carattere è ansible aggiungere uno spazio bianco alla fine della stringa originale o semplicemente ottenere l’ultimo carattere della stringa sul risultato.

String removeDuplicate (String s) {

  String result = ""; for (int i = 0; i < s.length(); i++){ if (i + 1 < s.length() && s.charAt(i) != s.charAt(i+1)){ result = result + s.charAt(i); } if (i + 1 == s.length()){ result = result + s.charAt(i); } } return result; } 

Non puoi È ansible creare una nuova stringa rimossa dai duplicati. Perché non stai usando StringBuilder (o StringBuffer, presumibilmente)?

Puoi scorrere la stringa e archiviare i caratteri univoci in un array char [], tenendo traccia di quanti personaggi unici hai visto. Quindi puoi creare una nuova stringa usando il costruttore String(char[], int, int) .

Inoltre, il problema è un po ‘ambiguo: i “duplicati” significano ripetizioni adiacenti? (In altre parole, cosa dovrebbe accadere con abcab ?)

Ok ragazzi, ho trovato un modo migliore per farlo

 public static void alpha(char[] finalname) { if (finalname == null) { return; } if (finalname.length <2) { return; } char empty = '\000'; for (int i=0; i 

Modo Oldschool (come abbiamo scritto un compito simile in Apple) [Basic, adattato a Java):

 int i,j; StringBuffer str=new StringBuffer(); Scanner in = new Scanner(System.in); System.out.print("Enter string: "); str.append(in.nextLine()); for (i=0;i 

Ecco un’altra logica che mi piacerebbe condividere. Inizi a confrontare da metà della lunghezza della stringa e vai indietro.

Test con: input = “azxxzy”; output = “ay”;

 String removeMidway(String input){ cnt = cnt+1; StringBuilder str = new StringBuilder(input); int midlen = str.length()/2; for(int i=midlen-1;i>0;i--){ for(int j=midlen;j
		      	

Questo è un altro approccio

 void remove_duplicate (char* str, int len) { unsigned int index = 0; int c = 0; int i = 0; while (c < len) { /* this is just example more check can be added for capital letter, space and special chars */ int pos = str[c] - 'a'; if ((index & (1< 

Un’altra ansible soluzione, nel caso in cui una stringa sia una stringa ASCII, è di mantenere una matrice di 256 elementi booleani per denotare l’aspetto del carattere ASCII in una stringa. Se un personaggio appare per la prima volta, lo teniamo e aggiungiamo al risultato. Altrimenti, basta saltarlo.

 public String removeDuplicates(String input) { boolean[] chars = new boolean[256]; StringBuilder resultStringBuilder = new StringBuilder(); for (Character c : input.toCharArray()) { if (!chars[c]) { resultStringBuilder.append(c); chars[c] = true; } } return resultStringBuilder.toString(); } 

Questo approccio funzionerà anche con la stringa Unicode. Hai solo bisogno di aumentare la dimensione dei chars .

Soluzione utilizzando JDK7:

 public static String removeDuplicateChars(final String str){ if (str == null || str.isEmpty()){ return str; } final char[] chArray = str.toCharArray(); final Set set = new LinkedHashSet<>(); for (char c : chArray) { set.add(c); } final StringBuilder sb = new StringBuilder(); for (Character character : set) { sb.append(character); } return sb.toString(); } 
  public static void main(String a[]){ String name="Madan"; System.out.println(name); StringBuilder sb=new StringBuilder(name); for(int i=0;i 
  String str = "[email protected]"; char[] c = str.toCharArray(); String op = ""; for(int i=0; i<=c.length-1; i++){ if(!op.contains(c[i] + "")) op = op + c[i]; } System.out.println(op); 
 public static String removeDuplicateChar(String str){ char charArray[] = str.toCharArray(); StringBuilder stringBuilder= new StringBuilder(); for(int i=0;i 
 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class RemoveDuplicacy { public static void main(String args[])throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Enter any word : "); String s = br.readLine(); int l = s.length(); char ch; String ans=" "; for(int i=0; i 
 import java.util.Scanner; public class dublicate { public static void main(String... a) { System.out.print("Enter the String"); Scanner Sc = new Scanner(System.in); String st=Sc.nextLine(); StringBuilder sb=new StringBuilder(); boolean [] bc=new boolean[256]; for(int i=0;i 
 public static void main(String[] args) { int i,j; StringBuffer str=new StringBuffer(); Scanner in = new Scanner(System.in); System.out.print("Enter string: "); str.append(in.nextLine()); for (i=0;i 

Questo è il miglioramento della soluzione suggerita da @Dave. Qui, sto implementando solo in loop singolo.

Riutilizziamo il ritorno del metodo set.add (T item) e lo aggiungiamo simultaneamente in StringBuffer se add ha successo

Questo è solo O (n). Non è necessario ripetere il ciclo.

 String string = "aabbccdefatafaz"; char[] chars = string.toCharArray(); StringBuilder sb = new StringBuilder(); Set charSet = new LinkedHashSet(); for (char c : chars) { if(charSet.add(c) ){ sb.append(c); } } System.out.println(sb.toString()); // abcdeftz 

La soluzione semplice è quella di iterare attraverso la stringa data e inserire ciascun carattere univoco in un’altra stringa (in questo caso, un risultato di variabile) se questa stringa non contiene quel particolare carattere. Infine restituisce la stringa di risultato come output.

Di seguito è riportato lo snippet di codice funzionante e testato per la rimozione di caratteri duplicati dalla stringa data che ha una complessità di tempo O (n).

 private static String removeDuplicate(String s) { String result=""; for (int i=0 ;i 

Se l'input è madam, l' output sarà pazzo .
Se l'input è anagramma, l' output sarà angrm

Spero che questo ti aiuti.
Grazie

Per la semplicità del codice, ho preso un input fondamentale, uno può prendere input usando anche la class Scanner

  public class KillDuplicateCharInString { public static void main(String args[]) { String str= "aaaabccdde "; char arr[]= str.toCharArray(); int n = arr.length; String finalStr=""; for(int i=0;i 
  public static void main (String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); String str = ""; char c; for(int i = 0; i < s.length(); i++) { c = s.charAt(i); str = str + c; s = s.replace(c, ' '); if(i == s.length() - 1) { System.out.println(str.replaceAll("\\s", "")); } } } 
 package com.st.removeduplicate; public class RemoveDuplicate { public static void main(String[] args) { String str1="shushil",str2=""; for(int i=0; i<=str1.length()-1;i++) { int count=0; for(int j=0;j<=i;j++) { if(str1.charAt(i)==str1.charAt(j)) count++; if(count >1) break; } if(count==1) str2=str2+str1.charAt(i); } System.out.println(str2); } 

}

pacchetto com.core.interview.client;

import java.util.LinkedHashSet;

import java.util.Scanner;

import java.util.Set;

public class RemoveDuplicateFromString {

 public static String DupRemoveFromString(String str){ char[] c1 =str.toCharArray(); Set charSet = new LinkedHashSet(); for(char c:c1){ charSet.add(c); } StringBuffer sb = new StringBuffer(); for (Character c2 : charSet) { sb.append(c2); } return sb.toString(); } public static void main(String[] args) { System.out.println("Enter Your String: "); Scanner sc = new Scanner(System.in); String str = sc.nextLine(); System.out.println(DupRemoveFromString(str)); } 

}

Spero che questo ti sia d’aiuto.

 public void RemoveDuplicates() { String s = "Hello World!"; int l = s.length(); char ch; String result = ""; for (int i = 0; i < l; i++) { ch = s.charAt(i); if (ch != ' ') { result = result + ch; } // Replacing space in all occurrence of the current character s = s.replace(ch, ' '); } System.out.println("After removing duplicate characters : " + result); }