Блог

общедоступная статическая строка frequencySort (строки) {

     String answer = "";
    
    HashMap<Character, Integer> map = new HashMap<>();
    
    for(int i = 0; i < s.length(); i  ) {
        
        map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)   1);
        
    }
    //System.out.println(map.get('l'));
    //System.out.println(map.get('e'));
    
    PriorityQueue<Character> q = new PriorityQueue<>(new Comparator<Character>() {

        @Override
        public int compare(Character o1, Character o2) {
            
            if(map.get(o1) == map.get(o2)) {
                //System.out.println("o1 - o2: "   o1   o2   " "   (o1 - o2));
                return o2 - o1;
            }
            
            else {
                return map.get(o2) - map.get(o1);
            }
        }
    });
    
    for(int i = 0; i < s.length(); i  ) {
        q.add(s.charAt(i));
    }
    
    while(!q.isEmpty()) {
        answer  = String.valueOf(q.poll());
    }
    
    return answer;
}
  

Мой код выглядит так, но я не знаю, почему иногда, когда частота становится одинаковой, но очередь не опрашивает символ, когда я пишу в компараторе, например, он выводится как ccwccwwwwwwwwwwwccwwcwwcwcw

Выглядит довольно хорошо! Не уверен в вашей ошибке, хотя это просто пройдет в Java без использования PriorityQueue:

 public final class Solution {
    public static final String frequencySort(
        String s
    ) {
        Map<Character, Integer> countmap = new HashMap<>();

        for (char character : s.toCharArray()) {
            countmap.put(character, 1   countmap.getOrDefault(character, 0));
        }


        List<Character>[] bucket = new List[s.length()   1];

        for (char key : countmap.keySet()) {
            int frequency = countmap.get(key);

            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }


            bucket[frequency].add(key);
        }

        StringBuilder sb = new StringBuilder();

        for (int pos = bucket.length - 1; pos >= 0; pos--)
            if (bucket[pos] != null)
                for (char character : bucket[pos])
                    for (int i = 0; i < pos; i  ) {
                        sb.append(character);
                    }


        return sb.toString();
    }
}
  

Вот некоторые из официальных решений LeetCode с комментариями:

 public String frequencySort(String s) {
        
    if (s == null || s.isEmpty()) return s;
    
    // Create a sorted Array of chars.
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    
    // Convert identical chars into single Strings.
    List<String> charStrings = new ArrayList<String>();
    StringBuilder currentString = new StringBuilder();
    currentString.append(chars[0]);
    for (int i = 1; i < chars.length; i  ) {
        if (chars[i] != chars[i - 1]) {
            charStrings.add(currentString.toString());
            currentString = new StringBuilder();
        }
        currentString.append(chars[i]);
    }
    charStrings.add(currentString.toString());
        
    // Our comparator is (a, b) -> b.length() - a.length().
    // If a is longer than b, then a negative number will be returned
    // telling the sort algorithm to place a first. Otherwise, a positive
    // number will be returned, telling it to place a second.
    // This results in a longest to shortest sorted list of the strings.
    Collections.sort(charStrings, (a, b) -> b.length() - a.length());
    
    // Use StringBuilder to build the String to return.
    StringBuilder sb = new StringBuilder();
    for (String str : charStrings) sb.append(str);
    return sb.toString();
}
  

 public String frequencySort(String s) {

    // Count up the occurances.
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0)   1);
    }
            
    // Make a list of the keys, sorted by frequency.
    List<Character> characters = new ArrayList<>(counts.keySet());        
    Collections.sort(characters, (a, b) -> counts.get(b) - counts.get(a));

    // Convert the counts into a string with a sb.
    StringBuilder sb = new StringBuilder();
    for (char c : characters) {
        int copies = counts.get(c);
        for (int i = 0; i < copies; i  ) {
            sb.append(c);
        }
    }
    return sb.toString();
}
  

 public String frequencySort(String s) {
        
    if (s == null || s.isEmpty()) return s;
    
    // Count up the occurances.
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0)   1);
    }
    
    int maximumFrequency = Collections.max(counts.values());
    
    // Make the list of buckets and apply bucket sort.
    List<List<Character>> buckets = new ArrayList<>();
    for (int i = 0; i <= maximumFrequency; i  ) {
        buckets.add(new ArrayList<Character>());
    }
    for (Character key : counts.keySet()) {
        int freq = counts.get(key);
        buckets.get(freq).add(key);
    }

    // Build up the string. 
    StringBuilder sb = new StringBuilder();
    for (int i = buckets.size() - 1; i >= 1; i--) {
        for (Character c : buckets.get(i)) {
            for (int j = 0; j < i; j  ) {
                sb.append(c);
            }
        }
    }
    return sb.toString();
}
  

Это решение использует очередь приоритетов, аналогичную вашей (было в комментарии к этой ссылке):

 class Solution {
    public String frequencySort(String s) {
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
                new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        Map<Character, Integer> frequency = new HashMap<>();
        for (Character c : s.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0)   1);
        }
        maxHeap.addAll(frequency.entrySet());
        StringBuilder sb = new StringBuilder();
        while (maxHeap.size() > 0) {
            Map.Entry<Character, Integer> entry = maxHeap.remove();
            for (int i = 0; i < entry.getValue(); i  ) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }
}
  

Ссылки

• Для получения дополнительной информации, пожалуйста, обратитесь к доске обсуждений, где вы можете найти множество хорошо объясненных принятых решений на различных языках, включая алгоритмы низкой сложности и асимптотический анализ времени выполнения / памяти^{1, 2}.