Наименее повторяющийся символ в строке

Я пытаюсь найти наименее повторяющийся символ в строке, он работает для некоторых входных данных, но не работает для некоторых входных данных.

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, и это правильно.

ваша проблема связана с этим условием: вы не печатаете char с наименьшим количеством вхождений, только char только с одним вхождением: if (map.get(ch) == 1)

Stultuske 29.05.2019 09:42

Что вы подразумеваете под «наименее повторяющимся символом»? Тот, который имеет наименьшее количество вхождений? Как это объясняет, что «aabbcc» производит «abc»?

Abhijit Sarkar 29.05.2019 09:44

@AbhijitSarkar, потому что все они имеют одинаковое количество вхождений

Stultuske 29.05.2019 09:45

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

Abhijit Sarkar 29.05.2019 09:47

Для подсчета вхождений рассмотрите возможность использования map.merge(ch, 1, Integer::sum) вместо if-else

Alex Salauyou 29.05.2019 09:47

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

Matthew 29.05.2019 10:17
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
2
6
1 298
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Ответ принят как подходящий

Как я уже прокомментировал, вы проверяете только символы, которые встречаются только один раз, а не наименьшее количество.

Вы можете изменить свой код следующим образом:

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), как в вашем решении

Alex Salauyou 29.05.2019 09:52

@AlexSalauyou да, но, учитывая исходный код, вероятность того, что ОП поймет этот код, чтобы найти свою ошибку, будет намного выше. Ничто в исходном посте не говорит о том, что он умеет работать с потоками, так зачем его еще больше смущать?

Stultuske 29.05.2019 09:53

@AlexSalauyou, разве твой код не всегда возвращает только один символ? Насколько я понимаю, он должен возвращать все символы с наименьшим количеством вхождений, например: для aabbccdddd он должен возвращаться abc

Amongalen 29.05.2019 09:59

@Amongalen, ты прав, я просто показываю подход к упрощению

Alex Salauyou 29.05.2019 10:02

Причина, по которой ваш код не работает так, как вам хотелось бы, заключается в том, что ваш последний блок кода печатается только в том случае, если символ повторяется один и только один раз:

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]

как это соответствует требованиям ОП? он печатает их все, а не только те, которые встречаются реже всего

Stultuske 29.05.2019 09:58

Приношу свои извинения, я обновил свой ответ, включив в него полный код.

Matthew 29.05.2019 10:12

Ваш код все еще имеет серьезные недостатки. добавьте несколько символов, которые встречаются только один раз, и он по-прежнему будет печатать только x.: Символ x повторяется наименьшее количество раз в тексте kambcxdabcdalbcdacd

Stultuske 29.05.2019 10:18

Спасибо за исправление, теперь он должен работать правильно и возвращать правильный массив Character объектов. Хотя это не имеет значения, поскольку к этому моменту ОП далеко ушел, но для меня это все еще достойное упражнение.

Matthew 29.05.2019 10:54

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

    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

Другие вопросы по теме