функция удаления повторяющихся символов в строке

Question

Следующий код пытается удалить любые повторяющиеся символы в строке. Я не уверен, что код правильный. Кто-нибудь может помочь мне поработать с кодом (т. Е. Что на самом деле происходит при совпадении символов)?

public static void removeDuplicates(char[] str) {
  if (str == null) return;
  int len = str.length;
  if (len < 2) return;
  int tail = 1;
  for (int i = 1; i < len; ++i) {
    int j;
    for (j = 0; j < tail; ++j) {
      if (str[i] == str[j]) break;
    }
    if (j == tail) {
      str[tail] = str[i];
      ++tail;
    }
  }
  str[tail] = 0;
}

Answer 1

Функция выглядит хорошо для меня.Я написал встроенные комментарии.Надеюсь, это поможет:

// function takes a char array as input.
// modifies it to remove duplicates and adds a 0 to mark the end
// of the unique chars in the array.
public static void removeDuplicates(char[] str) {
  if (str == null) return; // if the array does not exist..nothing to do return.
  int len = str.length; // get the array length.
  if (len < 2) return; // if its less than 2..can't have duplicates..return.
  int tail = 1; // number of unique char in the array.
  // start at 2nd char and go till the end of the array.
  for (int i = 1; i < len; ++i) { 
    int j;
    // for every char in outer loop check if that char is already seen.
    // char in [0,tail) are all unique.
    for (j = 0; j < tail; ++j) {
      if (str[i] == str[j]) break; // break if we find duplicate.
    }
    // if j reachs tail..we did not break, which implies this char at pos i
    // is not a duplicate. So we need to add it our "unique char list"
    // we add it to the end, that is at pos tail.
    if (j == tail) {
      str[tail] = str[i]; // add
      ++tail; // increment tail...[0,tail) is still "unique char list"
    }
  }
  str[tail] = 0; // add a 0 at the end to mark the end of the unique char.
}

Answer 2

Ваш код, извините, очень похож на C.

Java String - это не char[].Вы говорите, что хотите удалить дубликаты из String, но вместо этого берете char[].

Завершено ли это char[] \0?Не похоже, потому что вы берете все .length массива.Но тогда ваш алгоритм пытается \0 -определить часть массива.Что произойдет, если в массивах нет дубликатов?

Ну, как написано, ваш код на самом деле выбрасывает ArrayIndexOutOfBoundsException в последней строке!\0 нет места, потому что все слоты заняты!

Вы можете добавить проверку, чтобы не добавлять \0 в этом исключительном случае, но тогда как вы планируете использовать этот код в любом случае?Планируете ли вы иметь strlen -подобную функцию для поиска первого \0 в массиве?А что будет, если их нет?(из-за уникального исключительного случая, описанного выше?).

Что произойдет, если оригинал String / char[] содержит \0?(кстати, это вполне допустимо в Java, см. JLS 10.9. Массив символов не является строкой )

Результатом будет беспорядок, и все потому, что вы хотите это сделатьвсе в стиле C и без дополнительного буфера.Вы уверены, что вам действительно нужно это сделать?Почему бы не работать с String, indexOf, lastIndexOf, replace и всеми высокоуровневыми API String?Это слишком медленно, или вы только подозреваете, что это так?

«Преждевременная оптимизация - корень всех зол».Извините, но если вы даже не можете понять, что делает оригинальный код, то выяснить, как он будет вписываться в большую (и более сложную) систему, будет кошмаром.

---

Мое минимальное предложениесделать следующее:

• Сделать так, чтобы функция брала и возвращала String, то есть public static String removeDuplicates(String in)
• Внутренне, работает с char[] str = in.toCharArray();
• Заменитьпоследняя строка на return new String(str, 0, tail);

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

---

В качестве альтернативы, вы можетеиспользуйте StringBuilder как таковой:

static String removeDuplicates(String s) {
    StringBuilder noDupes = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        String si = s.substring(i, i + 1);
        if (noDupes.indexOf(si) == -1) {
            noDupes.append(si);
        }
    }
    return noDupes.toString();
}

Обратите внимание, что это по сути тот же алгоритм, что и у вас, но гораздо чище и без большого количества маленьких угловых случаев и т. д.

Answer 3

С учетом следующего вопроса:

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

Поскольку одна или две дополнительные переменные подходят, но буфер не разрешен, вы можетеимитировать поведение хэш-карты, используя вместо этого целое число для хранения битов.Это простое решение работает на O (n), что быстрее, чем у вас.Кроме того, он не является концептуально сложным и на месте:

    public static void removeDuplicates(char[] str) {
        int map = 0;
        for (int i = 0; i < str.length; i++) {
            if ((map & (1 << (str[i] - 'a'))) > 0) // duplicate detected
                str[i] = 0;
            else // add unique char as a bit '1' to the map
                map |= 1 << (str[i] - 'a');
        }
    }

Недостатком является то, что дубликаты (которые заменяются на 0) не будут размещаться в конце массива str [].Однако это можно легко исправить, выполнив цикл в последний раз.Кроме того, целое число может содержать только обычные буквы.

Answer 4

private static String removeDuplicateCharactersFromWord(String word) {

    String result = new String("");

    for (int i = 0; i < word.length(); i++) {
        if (!result.contains("" + word.charAt(i))) {
            result += "" + word.charAt(i);
        }
    }

    return result;
}

Answer 5

Это моё решение.

Алгоритм в основном такой же, как и в книге «Взлом интервью», откуда взято это упражнение, но я попытался немного его улучшить и сделать кодболее понятно:

public static void removeDuplicates(char[] str) {
        // if string has less than 2 characters, it can't contain
        // duplicate values, so there's nothing to do
        if (str == null || str.length < 2) {
            return;
        }

        // variable which indicates the end of the part of the string 
        // which is 'cleaned' (all duplicates removed)
        int tail = 0;

        for (int i = 0; i < str.length; i++) {
            boolean found = false;

            // check if character is already present in
            // the part of the array before the current char
            for (int j = 0; j < i; j++) {
                if (str[j] == str[i]) {
                    found = true;
                    break;
                }
            }

            // if char is already present
            // skip this one and do not copy it
            if (found) {
                continue;
            }

            // copy the current char to the index 
            // after the last known unique char in the array
            str[tail] = str[i];
            tail++;
        }

        str[tail] = '\0';
    }

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

Answer 6

char[] chars = s.toCharArray();
    HashSet<Character> charz = new HashSet<Character>();

    for(Character c : s.toCharArray() )
    {
        if(!charz.contains(c))
        {
            charz.add(c);
            //System.out.print(c);
        }
    }

    for(Character c : charz)
    {
        System.out.print(c);
    }

Answer 7

public String removeDuplicateChar(String nonUniqueString) {
    String uniqueString = "";
    for (char currentChar : nonUniqueString.toCharArray()) {
        if (!uniqueString.contains("" + currentChar)) {
            uniqueString += currentChar;
        }
    }

    return uniqueString;
}

Answer 8

Метод подстроки.Конкатенация выполняется с помощью .concat(), чтобы избежать выделения дополнительной памяти для левой и правой руки +.Примечание. При этом удаляются даже повторяющиеся пробелы.

private static String withoutDuplicatesSubstringing(String s){

        for(int i = 0; i < s.length(); i++){
          String sub = s.substring(i+1);
          int index = -1;
          while((index = sub.toLowerCase().indexOf(Character.toLowerCase(s.charAt(i)))) > -1 && !sub.isEmpty()){
              sub = sub.substring(0, index).concat(sub.substring(index+1, sub.length()));
          }
          s = s.substring(0, i+1).concat(sub);
        }
        return s;
    }

Контрольный пример:

String testCase1 = "nanananaa! baaaaatmaan! batman!";

Выход: na! btm

Answer 9

Я понимаю, что это вопрос Java, но так как у меня есть хорошее решение, которое может вдохновить кого-то преобразовать это в Java, во что бы то ни стало.Также мне нравятся ответы, в которых для общих проблем доступны разные языковые представления.

Так что вот решение Python, которое является O (n) и также поддерживает весь диапазон ASCII.Конечно, он не обрабатывает 'a' и 'A' как одно и то же:

Я использую 8 х 32 бита в качестве хэш-карты:

Также вводом является строковый массив с использованием дедупликации (список('некоторая строка'))

def dedup(str):
    map = [0,0,0,0,0,0,0,0]
    for i in range(len(str)):
        ascii = ord(str[i])
        slot = ascii / 32
        bit = ascii % 32
        bitOn = map[slot] & (1 << bit)
        if bitOn:
            str[i] = ''
        else:
            map[slot] |= 1 << bit

    return ''.join(str)

также более питонский способ сделать это, используя набор:

def dedup(s):
    return ''.join(list(set(s)))

Answer 10

public static void main (String [] args)
    {
        String s = "aabbbeeddsfre";//sample string
        String temp2="";//string with no duplicates
        HashMap<Integer,Character> tc = new HashMap<Integer,Character>();//create a hashmap to store the char's
        char [] charArray = s.toCharArray();
        for (Character c : charArray)//for each char
        {
            if (!tc.containsValue(c))//if the char is not already in the hashmap
                {
                    temp2=temp2+c.toString();//add the char to the output string
                    tc.put(c.hashCode(),c);//and add the char to the hashmap
                }
        }

        System.out.println(temp2);//final string
    }

вместо HashMap Я думаю, что мы можем использовать Set тоже.