在字符串中查找第 k 个频率字母

Question

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

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

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;
}

}

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

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

Answer 1

维护两个地图。

首先，在常规 HashMap 中将 char 映射到 int（即 char 到频率）。
其次，在 TreeMap 中将 int 映射到 List（即频率到具有该频率的字符）。

一一读取所有输入字符并更新两个映射。完成输入后，通过 TreeMap 获取列表。

从最大频率开始，

如果该列表少于 k 个元素（例如，等于 m），则转到下一个并寻找 (k - m)^th 元素。
另一方面，如果列表中有超过 k 个元素，则 return 是列表中的第一个元素，因为有多个 k^th 出现次数最多的元素。

Answer 2

o(n) 时间和常数的解 space。

假设它只包含字符。

伪代码（手机写的，没有IDE）

1) create a data structure of
Frequency
 Char ch,
 int v
2) create an array (frqy) of 52 length and type Frequency
2.1 initialize each of the 52 object with character a-zA-Z

3) itterate over each character (ch) in the string
3.1) check if (int)ch <=122 and >= 96
  Then  increment the frequency of  the frqy array at index (int)ch - 96

3.3) check if (int)ch <=90 and >= 65
  Then  increment the frequency of  the frqy array at index (int)ch - 65+26

4 ) sort the array based on frequency  and now you have the answer

Answer 3

这是一个流媒体解决方案：

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


public class Whosebug {

  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);
    }

  }
}

Answer 4

使用 TreeMap 不会有太大帮助，因为它是按键而不是值排序的。

这是我的简单算法：

收集有关某个字符在给定字符串中出现多少次的信息。
将其存储在字符和频率的映射中。
检索值（频率）并反向排序。
从这个反向排序的值中选择第三个值（因为你想要第三高的频率）。
从地图中找到所有具有此频率的键（字符）并打印它们。

这是一个基于此算法的工作程序：

    String str = "aabbddddccc";
    Map<Character, Integer> map = new HashMap<>();
    while (!str.isEmpty()) {
        char ch = str.charAt(0);
        String[] arr = str.split(Character.toString(ch));
        map.put(ch, arr.length == 0 ? str.length() : arr.length - 1);
        str = String.join("", arr);         
    }
    System.out.println(map);
    List<Integer> values = new ArrayList<>(map.values().stream().sorted().collect(Collectors.toSet()));
    Collections.reverse(values);
    map.keySet().stream().filter(e -> map.get(e) == values.get(3)).forEach(System.out::println);

Answer 5

我们将使用映射来计算频率，然后将计数和字符存储在成对列表中。
以自定义方式（基于字符数）对列表进行排序（使用比较器或 lambda）

从列表中检索第 K 个值。

import java.util.*;
import java.lang.*;
import java.io.*;
class Main{
    static class Pair{
    char first;
    int second;
    Pair(char first,int second){
        this.first=first;
        this.second=second;
    }
}
public static void main(String[] args) {
    TreeMap<Character,Integer> m = new TreeMap<>();    
    String s;
    int k;
    for(int i=0;i<s.length();i++){
        char ch = s.charAt(i);
        int x=0;
        if(m.containsKey(ch))
            x=m.get(ch);
        m.put(ch,x+1);
    }
    ArrayList<Pair> list = new ArrayList<Pair>();
    for(Map.Entry<Character,Integer> i : m.entrySet()){
        w.println(i.getKey() +" : "+i.getValue());
        list.add(new Pair(i.getKey(),i.getValue()));
    }
    Collections.sort(list, (a,b)->{if(a.second>=b.second) return -1; else return 1;});
    System.out.println(list.get(k-1).first);
}

}

为了确保你有第k个频繁元素，你可以使用hashSet来计算唯一频率的数量，如果有可能有第k个频率。

live 运行代码示例： https://ideone.com/p34SDC

Answer 6

下面是不使用 java 8

的简单解决方案

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
class TestClass {
public static void main(String args[]) throws Exception {
    // ma("aaabbacccd",3);
    // ma("aaabbacccbbbd",4);
    ma("aabbcd", 1);
}

private static void ma(String s, int k) {
    TreeMap<Character, Integer> map = new TreeMap<>();
    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        } else {
            map.put(s.charAt(i), 1);
        }
    }
    System.out.println(map.toString());
    Set<Entry<Character, Integer>> set = map.entrySet();
    List<Entry<Character, Integer>> list = new ArrayList<>(set);
    Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
        public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
            return o2.getValue().compareTo(o1.getValue());
        }
    });
    Set<Integer> ls = new LinkedHashSet<>();
    System.out.println("after sorting by value-----");
    for (Entry<Character, Integer> e : list) {
        System.out.println("key: " + e.getKey() + " value: " + e.getValue());
        ls.add(e.getValue());
    }
    System.out.println("removed duplicate from value array --------" + ls.toString());
    System.out.println(new ArrayList<>(ls).get(k - 1));
    for (Entry<Character, Integer> e1 : list) {
        if (e1.getValue().equals(new ArrayList<>(ls).get(k - 1))) {
            System.out.println(e1.getKey());
            break;
        }
    }
}

Answer 7

这在在线测试中非常方便，因为它是使用两张地图的非常简单的解决方案。我们首先创建一个字符频率哈希图。使用这个我们创建频率特征树图，仅当具有较小值时才将元素插入树图中（这是为了处理有多个字符具有相同的频率）。制作树图后（已经按频率递增排序），我们只打印与第 k 个最高频率对应的字符。

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception{
    String s="1112229999955555777777777";
    HashMap<Character,Integer> hm= new HashMap<Character,Integer>();
    for(int i=0;i<s.length();i++){
        char cur=s.charAt(i);
        if(!hm.containsKey(cur)){
            hm.put(cur,0);
        }
        hm.put(cur,hm.get(cur)+1);
    }
    TreeMap<Integer,Character> tm= new TreeMap<Integer,Character>();

    for(Map.Entry<Character,Integer> entry:hm.entrySet()){
        int x=entry.getValue();
        char cur=entry.getKey();
        if(!tm.containsKey(x)){
            tm.put(x,cur);
        }
        else{
            if(cur<tm.get(x))
                tm.put(x,cur);
        }

    }

    int k=2; // print the kth most frequent character. If there are multiple, print the one with lesser value
    int tar=tm.size()-k;
    if(tar<0) System.out.println("-1");
    else{
    int d=0;
    for(Map.Entry<Integer,Character> entry: tm.entrySet()){

        int x=entry.getKey();
        char cur=entry.getValue();
        //System.out.println(cur+" "+x);
        if(d++==tar)  {
            System.out.println("ans- "+cur);
            break; // we have found the requried character, so break
        }
    }

    }

}
}

Answer 8

static String getNthlargestFrequency(String str, int K) {
    char[] charArr = str.toCharArray();     
    String result = "-1"; //if nth frequency doesn't exist
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (char value : charArr) {
        if (map.containsKey(value)) {
            map.put(value, map.get(value) + 1);
        } else {
            map.put(value, 1);
        }
    }
    // sort map on value basis [desc]
    System.out.println("Original map" + map);
    Map sorted = map.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
            .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey, (e1, e2) -> e2, LinkedHashMap::new));
    //get character with nth maximum frequency
    Optional<Entry<Integer, Character>> entry = sorted.entrySet().stream().skip(K - 1).findFirst();
    if (entry.isPresent()) {
        result = ""+entry.get().getValue();
    }
    return result;
}

注：

如果有多个字符具有相同的第 n 个频率，则返回最后一个字符。

Answer 9

String str = scanner.next();
int k = scanner.nextInt();
HashMap <Character, Integer> hash = new HashMap();
int len = str.length();
Set <Integer> set = new TreeSet < > ();
for (int i = 0; i < len; i++) {
  Integer count = hash.get(str.charAt(i));
  if (count == null) {
    count = 0;
  }
  hash.put(str.charAt(i), count + 1);
} //iterate the entire map
for (Map.Entry < Character, Integer > h: hash.entrySet()) {
  set.add(h.getValue());
}
int length = set.size();
if (k > length) {
  System.out.println("-1");
} else {
  System.out.println(set);
  Iterator < Integer > it = set.iterator();
  int j = 0;
  Integer integer = null;
  while (it.hasNext() && j <= length - k) {
    integer = it.next();
    j++;
  }
  int x = integer;
  for (Map.Entry < Character, Integer > h: hash.entrySet()) {
    if (h.getValue() == integer) {
      System.out.println(h.getKey());
      break;
    }
  }
}

Answer 10

使用自定义的 HashMap 和优先队列解决了 Class。

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class kth_largest_in_a_string {

    static class myclass {
        int count;
        char ch;

        myclass(int count, char ch) {
            this.count = count;
            this.ch = ch;
        }
    }

    public static Character helper(String input, int k) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < input.length(); i++) {
            if (!map.containsKey(input.charAt(i))) {
                map.put(input.charAt(i), 1);
            } else {
                map.put(input.charAt(i), map.get(input.charAt(i)) + 1);
            }
        }
        PriorityQueue<myclass> pq = new PriorityQueue<>(input.length(), new Comparator<myclass>() {
            public int compare(myclass a, myclass b) {
                return b.count - a.count;
            }
        });
        for (HashMap.Entry<Character, Integer> entry : map.entrySet()) {
            pq.add(new myclass(entry.getValue(), entry.getKey()));
        }
        for (int i = 0; i < k - 1; i++)
            pq.remove();
        myclass ans = pq.remove();
        return ans.ch;
    }

    public static void main(String[] args) {
        System.out.println(helper("aaabbacccd", 3));
    }
}

Answer 11

public class MyStringDemo {

    public static void main(String[] args) {
        try {
            Scanner scanner = new Scanner(System.in);
            System.out.print("Enter Test Case Numbers: ");
            int T = Integer.parseInt(scanner.nextLine());
            int testCases[] = new int[T];
            
            for (int i=0 ; i < testCases.length; i++) {
                System.out.print("Enter String: ");
                String str = scanner.nextLine();
                System.out.print("Enter Kth String Number: ");
                int K = Integer.parseInt(scanner.nextLine());
                String result = getKthFrequency(str, K);
                System.out.println(result);
            }
        }catch (Exception e) {
            e.printStackTrace();
        }
    }

    static String getKthFrequency(String str, int K) {
        HashMap<Character, Integer> hp = new HashMap<Character, Integer>();
        char chs[] = str.toCharArray();
        
        for (char c : chs) {
            if (hp.containsKey(c)) {
                hp.put(c, hp.get(c) + 1);
            } else {
                hp.put(c, 1);
            }
        }
        char ch = 'z';
        boolean flag = false;
        for (Map.Entry<Character, Integer> val : hp.entrySet()) {
            if (K == val.getValue()) {
                if (ch > val.getKey()) {
                    ch = val.getKey();
                    flag = true;
                }
                return ch + "";
            }
            flag = false;
        }
        return flag == true ? ch + "" : "-1";
    }
}

在字符串中查找第 k 个频率字母

Finding kth frequency letter in a string of characters

java

sorting

data-structures

treemap

注：