Вопросы Теги

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

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

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;
}
30
задан Ryan Berger 17 November 2011 в 01:17
поделиться

3 ответа

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

// 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.
}
43
ответ дан 27 November 2019 в 22:59
поделиться

Ваш код, к сожалению, очень похож на C.

Строка Java не является 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 , то есть общедоступную статическую строку 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();
}

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

33
ответ дан 27 November 2019 в 22:59
поделиться

Это было бы намного проще, если бы вы просто перебирали массив и добавляли все новые символы в список, а затем повторно запускали этот список.

При таком подходе вам необходимо перетасовать массив по мере его прохождения и, в конечном итоге, изменить его размер до подходящего размера в конце.

0
ответ дан 27 November 2019 в 22:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: