Я пытаюсь найти наименее повторяющийся символ в строке, он работает для некоторых входных данных, но не работает для некоторых входных данных.
Map<Character, Integer> map = new HashMap<Character, Integer> ();
String s = "abcdabcdabcdacd";
char[] chars = s.toCharArray();
for (Character ch: chars) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
Set<Character> keys = map.keySet();
for (Character ch: keys) {
if (map.get(ch) ==1) {
System.out.println(ch + " ");
}
}
Я ожидаю, что вывод будет b, но он ничего не показывает. Если я даю aabaa в качестве ввода, тогда он показывает b, и это правильно.
Что вы подразумеваете под «наименее повторяющимся символом»? Тот, который имеет наименьшее количество вхождений? Как это объясняет, что «aabbcc» производит «abc»?
@AbhijitSarkar, потому что все они имеют одинаковое количество вхождений
Итак, вы хотите найти наименее повторяющийся символ с во множественном числе. Почему бы не создать карту частот и не выполнить второй проход, чтобы найти все ключи с минимальными значениями? Временная сложность O(n) в худшем случае, если все символы уникальны.
Для подсчета вхождений рассмотрите возможность использования map.merge(ch, 1, Integer::sum)
вместо if-else
Для будущих вопросов я бы рекомендовал подождать немного дольше, чем 20 минут, прежде чем принимать ответ, чтобы вы могли увидеть все свои варианты, прежде чем выбрать первый попавшийся. Я считаю, что мой ответ самый атомарный, но не обязательно лучший, это решать другим.
Как я уже прокомментировал, вы проверяете только символы, которые встречаются только один раз, а не наименьшее количество.
Вы можете изменить свой код следующим образом:
public class PrintB {
public static void main(String[] args) {
Map<Character, Integer> map = new HashMap<>();
String s = "abcdabcdabcdacd";
char[] chars = s.toCharArray();
for (Character ch: chars) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
Set<Character> keys = map.keySet();
boolean broken = false;
for ( int i = 0; i < s.length(); i++ ) { // the max will be s.length()
for (Character ch : keys) {
if (map.get(ch) == i) { // this amount is checked for each char
System.out.println(ch + " ");
broken = true;
}
}
if ( broken ) {
i = s.length(); // sure, there are other ways to break out of the loop
}
}
}
}
можно сделать так же просто, как map.entrySet().stream().min( Comparator.comparingInt( Map.Entry::getValue ) ).get().getKey();
не требуя O (N ^ 2), как в вашем решении
@AlexSalauyou да, но, учитывая исходный код, вероятность того, что ОП поймет этот код, чтобы найти свою ошибку, будет намного выше. Ничто в исходном посте не говорит о том, что он умеет работать с потоками, так зачем его еще больше смущать?
@AlexSalauyou, разве твой код не всегда возвращает только один символ? Насколько я понимаю, он должен возвращать все символы с наименьшим количеством вхождений, например: для aabbccdddd
он должен возвращаться abc
@Amongalen, ты прав, я просто показываю подход к упрощению
Причина, по которой ваш код не работает так, как вам хотелось бы, заключается в том, что ваш последний блок кода печатается только в том случае, если символ повторяется один и только один раз:
for (Character ch: keys) {
if (map.get(ch) ==1) {
System.out.println(ch + " ");
}
Однако, используя метод Collections.min
, мы можем найти наименьшее значение карты, которое мы затем можем использовать для поиска символа, которому он принадлежит, из ключей карты. Вот полный код с контекстом:
/**
* @return an array of Character objects that have occured the
* least amount of times in the given {@code String} parameter.
* <i>Note that all whitespaces found within the {@code String} will be ignored </i>
*/
public static Character[] getLeastRepeatingCharacters(String text) {
Map<Character, Integer> map = new HashMap<Character, Integer> ();
/*
* Remove all whitespaces from the text as we don't
* want to include them in our comparison oprations
*/
text = text.replaceAll("\\s+","");
for (Character ch : text.toCharArray()) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
}
else if (ch != '\0') {
map.put(ch, 1);
}
}
/*
* Get map value that occurs the least amount of times
*/
int leastOccuranceValue = Collections.min(map.values());
java.util.List<Character> leastOccurances = new java.util.ArrayList<>();
/*
* Iterate through the map, find all characters that have
* occured the least amount of times and add them to a list
*/
for (java.util.Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(leastOccuranceValue)) {
leastOccurances.add(entry.getKey());
}
}
return leastOccurances.toArray(new Character[0]);
}
public static void main(String[] args) {
String text = "abcdabcdabcdacd";
Character[] leastRepeating = getLeastRepeatingCharacters(text);
String log = "Array of charactes that repeated the least amount of times in text '%s':%n%s";
System.out.printf(log, text, Arrays.toString(leastRepeating));
}
Выход:
Образец вашей строки:
Array of charactes that repeated the least amount of times in text 'abcdabcdabcdacd ':
[b]
Образец строки предоставлен Stultuske:
Array of charactes that repeated the least amount of times in text 'kambcxdabcdalbcdacd ':
[x, k, l, m]
как это соответствует требованиям ОП? он печатает их все, а не только те, которые встречаются реже всего
Приношу свои извинения, я обновил свой ответ, включив в него полный код.
Ваш код все еще имеет серьезные недостатки. добавьте несколько символов, которые встречаются только один раз, и он по-прежнему будет печатать только x.: Символ x повторяется наименьшее количество раз в тексте kambcxdabcdalbcdacd
Спасибо за исправление, теперь он должен работать правильно и возвращать правильный массив Character
объектов. Хотя это не имеет значения, поскольку к этому моменту ОП далеко ушел, но для меня это все еще достойное упражнение.
Вы должны прочитать всю карту, чтобы получить минимальное вхождение, поэтому вы не можете печатать в цикле, вместо этого вы должны собирать символы с минимальным вхождением, а затем печатать их.
public static void main(String[] args) {
Map<Character, Integer> map = new HashMap<>();
String s = "abcdaybcdabcdacdz";
char[] chars = s.toCharArray();
for (Character ch: chars) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
List<Character> reps = new ArrayList<>();
Integer count = chars.length;
Set<Entry<Character, Integer>> entries = map.entrySet();
for (Entry<Character, Integer> entry : entries) {
Integer n = entry.getValue();
Character c = entry.getKey();
if (n==count) {
reps.add(c);
}else if (n<count) {
reps = new ArrayList<>();
reps.add(c);
count = n;
}
}
for (Character character : reps) {
System.out.println(character);
}
}
Используя потоки, вы можете просто сделать:
final String s = "abcdabcdabcdacd";
String leastRepeated =
s.chars().mapToObj(i -> Character.toString((char) i)) // map to Stream<String>
.collect(Collectors.toMap(k -> k, v -> 1, Integer::sum)) // Map<String, Integer>
.entrySet().stream() // stream over map
.min(Comparator.comparing(Entry::getValue)) // comparing values in map
.get().getKey(); // get resp entry
который выводит:
b
ваша проблема связана с этим условием: вы не печатаете char с наименьшим количеством вхождений, только char только с одним вхождением: if (map.get(ch) == 1)