it-swarm-ru.tech

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

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

Например, строка 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);

    }

}

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

15
Ricco

Преобразуйте строку в массив char и сохраните ее в 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());
40
Dave

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

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

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

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;
}
4
Michele Vergnano

Использование Stream облегчает задачу.

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

Вот еще немного документации о Stream и все, что вы можете сделать с помощью Это : https://docs.Oracle.com/javase/8/docs/api/Java/util/stream/package-summary.html

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

3
Fundhor

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

2
Chris Dennett
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);
    }
}
1
HariKrishna

Я думаю, что работать таким образом было бы проще , Просто передайте строку этой функции, и работа сделана :).

private static void removeduplicate(String name)
{   char[] arr = name.toCharArray();
    StringBuffer modified =new StringBuffer();
    for(char a:arr)
    {
        if(!modified.contains(Character.toString(a)))
        {
            modified=modified.append(Character.toString(a)) ;
        }
    }
    System.out.println(modified);
}
1
vikram reddy

Вот улучшение ответа Дэйва .

Он использует 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
1
Andreas

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

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;

}
1
Chris

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

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

    }
}

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

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

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

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

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

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

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

Упражнения для обсуждения кодеров:

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

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

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

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

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

1
Eric Leschinski
    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);

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

1
user1901928
StringBuilder builderWord = new StringBuilder(Word);
 for(int index=0; index < builderWord.length(); index++) {
   for(int reverseIndex=builderWord.length()-1; reverseIndex > index;reverseIndex--) {
     if (builderWord.charAt(reverseIndex) == builderWord.charAt(index)) {
       builderWord.deleteCharAt(reverseIndex);
     }
   }
}
return builderWord.toString();
0
venkat

Простое решение состоит в том, чтобы перебрать данную строку и поместить каждый уникальный символ в другую строку (в данном случае, в переменную result), если эта строка не содержит этот конкретный символ. Наконец, вернуть строку result как выход.

Ниже приведен рабочий и проверенный фрагмент кода для удаления повторяющихся символов из заданной строки, которая имеет 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;
  }

Если ввод madam, то вывод будет mad.
Если ввод anagram, то вывод будет angrm

Надеюсь это поможет.
Спасибо

0
VRaj
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);
}
0
hemachandra

пакет com.core.interview.client;

import Java.util.LinkedHashSet;

импорт Java.util.Scanner;

import Java.util.Set;

открытый класс RemoveDuplicateFromString {

public static String DupRemoveFromString(String str){




    char[] c1 =str.toCharArray();

    Set<Character> charSet = new LinkedHashSet<Character>();

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

}

0
Manash Ranjan Dakua

Надеюсь, это поможет.

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);
}
0
Nagarjuna KR

есть массив, чтобы узнать, был ли символ уже записан или нет; если нет, добавьте это в строковый буфер. Обратите внимание, что я сделал это с учетом регистра; с массивом int вы всегда можете сделать это (в этом коде этого не сделано), чтобы также возвращать количество вхождений.

private static String removeDuplicates(String s) {

    int [] occurrences = new int[52];
    Arrays.fill(occurrences,0);

    StringBuffer deDupS = new StringBuffer();
    for(int i = 0; i < s.length(); i++) {
        if(s.charAt(i) >= 97) {
            if(occurrences[s.charAt(i) - 97] == 0) {
                deDupS.append(s.charAt(i));
                occurrences[s.charAt(i) - 97]++;
            }
        } else if(s.charAt(i) >= 65) {
            if(occurrences[s.charAt(i) - 65 + 26] == 0) {
                deDupS.append(s.charAt(i));
                occurrences[s.charAt(i) - 65 + 26]++;
            }
        }
    }

    return deDupS.toString();

}
0
Tech Junkie
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);

}

}

0
Pravesh Kumar Gupta

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

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

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

0
Alex Erohin
 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+"");

    }
0
user6012628
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());
    }
}
0
Abhishek Choubey
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);
        }

}
0
user6319208
public String removeDuplicates(String dupCharsString){
    StringBuffer buffer = new StringBuffer(dupCharsString);
    int step = 0;
    while(step <= buffer.length()){
        for( int i = step + 1; i < buffer.length(); i++ ){
            if( buffer.charAt(i) == buffer.charAt(step) ){
                buffer.setCharAt(i, ' ');
            }
        }
        step++;
    }
    return buffer.toString().replaceAll("\\s","");
}
0
Cesar Joel Ramos Cuetlach

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

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

Это просто O (n). Не нужно делать петлю снова.

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
0
nagendra547
String str1[] ="Hi helloo helloo  oooo this".split(" "); 

Set<String> charSet = new LinkedHashSet<String>();
for (String c: str1) 
{
       charSet.add(c); 
}
StringBuilder sb = new StringBuilder(); 
for (String character : charSet) 
{
       sb.append(character); 
}

System.out.println(sb.toString());
0
rahul dhokale
 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", ""));   
        }
    }
}
0
Chandan Jaiswal

Решение с использованием 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();
}
0
realPK
import Java.util.LinkedHashMap;
import Java.util.Map.Entry;

public class Sol {

    public static void main(String[] args) {
        char[] str = "bananas".toCharArray();
        LinkedHashMap<Character,Integer> map = new LinkedHashMap<>();
        StringBuffer s = new StringBuffer();

        for(Character c : str){
            if(map.containsKey(c))
                map.put(c, map.get(c)+1);
            else
                map.put(c, 1);
        }

        for(Entry<Character,Integer> entry : map.entrySet()){
            s.append(entry.getKey());
        }

        System.out.println(s);
    }

}
0
sarfaraz pathan

Oldschool way (как мы писали такие задачи в 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);
0
SEGStriker

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

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

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

0
Ted Hopp
    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);
0
Elamparuthi
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();
    }
0
Neeraj Gahlawat

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

Тест с: 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();
    }
0
Jak Ratiwanich

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

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


}
0
Delta Hex

Это другой подход 

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

Попробуйте это простое решение, используя концепцию Set collection: String str = "aabbcdegg";

    Set<Character>removeduplicates = new LinkedHashSet<>();
    char strarray[]= str.toCharArray();
    for(char c:strarray)
    {
        removeduplicates.add(c);
    }


    Iterator<Character> itr = removeduplicates.iterator();
    while(itr.hasNext())
    {
        System.out.print(itr.next());
    }
0
Tisa

Для простоты кода - я взял хардкорный ввод, можно взять ввод, используя класс 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);



    }
}
0
Nitesh