Удаление дубликатов из строки в Java

Question

Я пытаюсь выполнить итерацию по строке, чтобы удалить дубликаты символов.

Например, строка aabbccdef должна стать abcdef и струнный abcdabcd должен стать abcd

Вот то, что я до сих пор:

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

    } 

} 

Что такое лучший способ сделать это?

Answer 1

Преобразование строки в массив полукокса, и хранить его в LinkedHashSet. Это сохранит ваш заказ и удалит дубликаты. Что-то вроде:

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
Set<Character> charSet = new LinkedHashSet<Character>(); 
for (char c : chars) { 
    charSet.add(c); 
} 

StringBuilder sb = new StringBuilder(); 
for (Character character : charSet) { 
    sb.append(character); 
} 
System.out.println(sb.toString()); 

Answer 2

Создайте StringWriter. Запустите исходную строку, используя charAt (i) в цикле for. Ведение переменной типа char, сохраняющей последнее значение charAt. Если вы повторяете и значение charAt равно тому, что хранится в этой переменной, не добавляйте к StringWriter. Наконец, используйте метод StringWriter.toString() и получите строку и сделайте то, что вам нужно.

Answer 3

Вы не можете. Вы можете создать новую строку, у которой дубликаты удалены. Почему вы не используете StringBuilder (или StringBuffer, предположительно)?

Вы можете запустить строку и сохранить уникальные символы в массиве char [], отслеживая количество уникальных символов, которые вы видели. Затем вы можете создать новую строку с помощью конструктора String(char[], int, int).

Кроме того, проблема немного неоднозначна — делает “ дубликатов ” означает смежные повторения? (Другими словами, что должно произойти с abcab?)

Answer 4

Я бы воспользовался помощью LinkedHashSet. Удаляет дубликаты (поскольку мы используем Set, поддерживаем заказ, когда используем связанный список impl). Это своего рода грязное решение. может быть даже лучший способ.

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

Answer 5

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

Answer 6

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

, но вы не можете использовать его, если входной сигнал имеет те же элементы, или если его пустым!

Answer 7

Ладно, ребята, я нашел лучший способ сделать это

public static void alpha(char[] finalname) 
{ 
    if (finalname == null) 
    { 
     return; 
    } 

    if (finalname.length <2) 
    { 
     return; 
    } 

    char empty = '\000'; 
    for (int i=0; i<finalname.length-1; i++) 
    { 
     if (finalname[i] == finalname[i+1]) 
     { 
      finalname[i] = empty; 
     } 
    } 

    String alphaname = String.valueOf(finalname); 
    alphaname = alphaname.replace("\000", ""); 
    System.out.println(alphaname); 


} 

Answer 8

Попробуйте это простое решение:

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

Answer 9

OLDSCHOOL путь (как мы писали такую ​​задачу в компании Apple] [Basic, адаптировано к 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<str.length()-1;i++){ 
    for (j=i+1;j<str.length();j++){ 
     if (str.charAt(i)==str.charAt(j)) 
      str.deleteCharAt(j); 
    } 
} 
System.out.println("Removed non-unique symbols: " + str); 

Answer 10

Код для удаления повторяющихся символов в строке без использования дополнительного буфера. ПРИМЕЧАНИЕ. Одна или две дополнительные переменные являются точными.Дополнительный массив не является:

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 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()-=_+[]{}|;:',.<>/?`~"; 

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

    } 
} 

Как читать и говорить о коде выше:

1. Метод называется removeDupes принимает массив примитивных символов, называемых обрами.
2. arr возвращается как массив примитивных символов «по значению». Принятый arr - мусор, собранный в конце метода участника Main's removeDupes.
3. Сложность выполнения этого алгоритма - O (n) или, более конкретно, O (n + (малая константа)), константа - это уникальные символы во всем массиве примитивных символов.
4. CopyOfRange не увеличивает значительную сложность выполнения, поскольку только копирует небольшое постоянное количество элементов. Массив char, называемый arr, не проходит полностью.
5. Если вы передаете null в removeDupes, метод возвращает null.
6. Если вы передадите пустой массив примитивных символов или массив, содержащий одно значение, возвращается немодифицированный массив.
7. Метод removeDupes выполняется так же быстро, как это возможно физически, полностью используя кеш L1 и L2, поэтому Branch redirects are kept to a minimum.
8. Негрубованный компьютер стандартной версии 2015 года должен иметь возможность завершить этот метод с помощью примитивного массива символов, содержащего 500 миллионов символов в диапазоне от 15 до 25 секунд.

Объясните, как этот код работает:

Первая часть массива, переданного в используется в качестве хранилища для уникальных персонажей, которые в конечном счете возвращены. В начале функции ответ: «символы от 0 до 1» от 0 до хвоста.

Мы определяем переменную y вне цикла, потому что мы хотим найти первое место, где индекс массива, который мы рассматриваем, был дублирован в нашем репозитории. Когда найден дубликат, он вырывается и завершается, хвост y == возвращает false, а репозиторий не предоставляется.

, когда индекс x, который мы просматриваем, не представлен в нашем репозитории, тогда мы вытаскиваем его и добавляем в конец нашего репозитория по хвосту индекса и хвосту инкремента.

В конце мы возвращаем массив между точками 0 и хвостом, который должен быть меньше или равен длине исходного массива.

Говоря точки упражнения для кодера интервью:

Будет ли программа ведет себя по-разному, если изменить у ++ в ++ у? Почему или почему нет.

Является ли массив копией в конце, представляет собой другой «N» проход через весь массив, создающий сложность выполнения O (n * n) вместо O (n)? Почему или почему нет.

Можете ли вы заменить двойные равные на сравнение примитивных символов с .equals? Почему или почему нет?

Можно ли изменить этот метод для замены «по ссылке» вместо «теперь по значению»? Почему или почему нет?

Можете ли вы повысить эффективность этого алгоритма, сортируя хранилище уникальных значений в начале 'arr'? В каких обстоятельствах это будет более эффективно?

Answer 11

Вот еще одна логика, которую я хотел бы поделиться. Вы начинаете сравнивать с середины длины строки и идите назад.

Испытание с: 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<str.length()-1;j++){  
       if(str.charAt(i)==str.charAt(j)){ 
        str.delete(i, j+1); 
        midlen = str.length()/2; 
        System.out.println("i="+i+",j="+j+ ",len="+ str.length() + ",midlen=" + midlen+ ", after deleted = " + str); 
       } 
      } 
     }  
     return str.toString(); 
    } 

Answer 12

Подробнее об answer by Dave.

Он использует HashSet вместо чуть более дорогостоящего LinkedHashSet, и повторно использует chars буфера для результата, устраняя необходимость в StringBuilder.

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
Set<Character> 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 

Answer 13

Это еще один подход

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<<pos)) == 0) { 
      str[i++] = str[c]; 
      index |= (1<<pos); 
     } 
     c++; 
    } 
    str[i] = 0; 
} 

Answer 14

Другого возможным решение, в случае, если строка является строка ASCII-, является поддержание массива 256 логических элементов для обозначения ASCII внешнего вида символов в строке. Если персонаж появился впервые, мы сохраняем его и добавляем к результату. В противном случае просто пропустите его.

Этот подход также будет работать с строкой Unicode. Вам просто нужно увеличить размер chars.

Answer 15

Решение с использованием JDK7:

public static String removeDuplicateChars(final String str){ 

    if (str == null || str.isEmpty()){ 
     return str; 
    } 

    final char[] chArray = str.toCharArray(); 
    final Set<Character> 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(); 
} 

Answer 16

public static void main(String a[]){ 
     String name="Madan"; 
     System.out.println(name); 
     StringBuilder sb=new StringBuilder(name); 
     for(int i=0;i<name.length();i++){ 
      for(int j=i+1;j<name.length();j++){ 
      if(name.charAt(i)==name.charAt(j)){ 
       sb.deleteCharAt(j); 

      } 
      } 
     } 
    System.out.println("After deletion :"+sb+""); 

    } 

Answer 17

String str = "eamparuthik@gmail.com"; 
    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); 

Answer 18

public static String removeDuplicateChar(String str){ 
     char charArray[] = str.toCharArray(); 
     StringBuilder stringBuilder= new StringBuilder(); 
     for(int i=0;i<charArray.length;i++){ 
      int index = stringBuilder.toString().indexOf(charArray[i]); 
      if(index <= -1){ 
       stringBuilder.append(charArray[i]); 
      } 
     } 
     return stringBuilder.toString(); 
    } 

Answer 19

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<l; i++) 
      { 
       ch = s.charAt(i); 
       if(ch!=' ') 
        ans = ans + ch; 
       s = s.replace(ch,' '); //Replacing all occurrence of the current character by a space 
      } 

      System.out.println("Word after removing duplicate characters : " + ans); 
     } 

} 

Answer 20

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<st.length();i++) 
     { 
      int index=st.charAt(i); 
      if(bc[index]==false) 
      { 
       sb.append(st.charAt(i)); 
       bc[index]=true; 
      } 

     } 
     System.out.print(sb.toString()); 
    } 
} 

Answer 21

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<str.length()-1;i++) 
    { 
     for (j=1;j<str.length();j++) 
     { 
      if (str.charAt(i)==str.charAt(j)) 
       str.deleteCharAt(j); 
     } 
    } 
    System.out.println("Removed String: " + str); 
} 

Answer 22

Это улучшение на решение предложено @ Dave. Здесь я реализую только один цикл.

Давайте повторное возвращение из Set.add (T элемент) метод и добавить его одновременно в StringBuffer, если добавить успешна

Это просто O (п). Не нужно повторять цикл.

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
StringBuilder sb = new StringBuilder(); 
Set<Character> charSet = new LinkedHashSet<Character>(); 
for (char c : chars) { 
    if(charSet.add(c)){ 
     sb.append(c); 
    } 

} 
System.out.println(sb.toString()); // abcdeftz 

Answer 23

Простое решение для перебора заданной строки и поместить каждый уникальный символ в другую строку (в данном случае, переменный результата), если эта строка не содержит, что особенно character.Finally возвращает результат строка как выход.

Ниже приведен рабочий и проверенный фрагмент кода для удаления повторяющихся символов из заданной строки, которая имеет сложность времени O (n).

private static String removeDuplicate(String s) { 
     String result=""; 
     for (int i=0 ;i<s.length();i++) { 
      char ch = s.charAt(i); 
      if (!result.contains(""+ch)) { 
       result+=""+ch; 
      } 
     } 
     return result; 
    } 

Если вход сударыня, то выход будет ума.
Если вход анаграммы тогда выход будет angrm

Надеется, что это помогает.
Благодаря

Answer 24

Для простоты code- я взял хардкор вход, можно взять вход с помощью класса 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<n;i++) { 
      if(i==n-1){ 
       finalStr+=arr[i]; 
       break; 
      } 
      if(arr[i]==arr[i+1]) { 
       continue; 
      } 
      else { 
       finalStr+=arr[i]; 
      } 
     } 
     System.out.println(finalStr); 



    } 
} 

Answer 25

Использование потока делает его легким.

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

Вот еще некоторые документы о потоке и все, что вы можете сделать с это: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

«Описание» часть очень поучительно о преимуществах Streams.

Answer 26

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

Answer 27

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

} 

}

Answer 28

Для меня это выглядит как каждый пытается слишком трудно выполнить эту задачу. Все, о чем нас беспокоит, заключается в том, что он копирует 1 копию каждой буквы, если она повторяется. Тогда, поскольку нас беспокоит только то, повторяют ли эти символы один за другим, вложенные циклы становятся произвольными, поскольку вы просто можете просто сравнить позицию n с положением n + 1. Тогда, поскольку это только копирует вещи вниз, когда они разные, последний символ, вы можете либо добавить белое пространство в конец исходной строки, либо просто скопировать его, чтобы скопировать последний символ строки в результат.

Строка 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; 

}