java - 查找字符串中第 k 个出现频率的字母

Question

我这里有一个字符串“aaabbacccd” count[a]=4 count[b]=2 count[c]=3 和 count[d]=1 。我必须找到频率第 n 大的字符。在上面的字符串中，出现频率第三高的字符是 b(因为 1<2<3<4)并且 count[b]=2

直接的解决方案是将字符与频率存储在 map 中，并使用按值排序集合的方法对值进行排序，如下所示

public class MapUtil {
public static <K, V extends Comparable<? super V>> Map<K, V> 
    sortByValue(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo( o2.getValue() );
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }
    return result;
}

}

我尝试使用树形图来解决这个问题，以根据计数按排序顺序维护字符。但我最终得到的只是违反了平等性并与约束进行比较，因此我的 map 以不一致的值结束。

那么这个问题不能用树形图或任何其他数据结构以最佳方式解决吗？

Answer 1

这是一个流解决方案:

import java.util.Collections;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;


public class StackOverflow {

  private static class S46330187 {
    public static void main(String[] args) {
      //prints b
      System.out.println(kthMostFrequentChar("aaabbacccd",3));
      //prints b
      System.out.println(kthMostFrequentChar("aaabbacccbbbd",1));
      //prints e
      System.out.println(kthMostFrequentChar("aaabbbcccdddeee",5));

    }

    private static Character kthMostFrequentChar(final String string, final int kth) {
      Map<Integer, Long> counts = string.chars()
          .boxed()
          .collect(Collectors.groupingBy(
              Function.identity(),
              Collectors.counting()
          ));
      return counts.entrySet()
          .stream()
          .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
          .map(e->(char)e.getKey().intValue())
          .limit(kth)
          .reduce((l,r)->r)
          .orElseThrow(IllegalArgumentException::new);
    }

  }
}