查找java中字符串中字符频率的有效方法：O（n）
在最近的一次采访中，我被要求写下面的程序。 找出给定字符串中频率最小的字符？ 所以我尝试通过使用charAt迭代字符串并将字符作为键存储在HashMap中，并将出现次数作为其值。 现在，我必须迭代Map以找到最低元素。
是否有一种更有效的方法来做到这一点，显然上面的一个太强烈了我猜。
更新和另一种解决方案
经过一些思考过程和答案后，我认为最好的时间是O（n）。 在第一次迭代中，我们将不得不逐个字符地迭代字符串，然后将它们的频率存储在特定位置的数组中（字符是一个int），同时有两个临时变量，它们保持最少的计数和相应的字符。因此，当我转到下一个字符并将其频率存储在arr [char] = arr [char] +1中;同时我将检查temp varible是否具有大于此值的值，如果是，那么temp变量将是这个值，而char也将是这一个。这样我认为我们不需要第二次迭代来找到最小的并且也不需要排序我猜
…. Wat说？ 或者更多解决方案
我使用数组而不是哈希映射。 如果我们仅限于ascii，那只是256个条目; 如果我们使用Unicode，64k。 无论哪种方式都不是不可能的大小。 除此之外，我不知道你如何改进你的方法。 我试图想出一些聪明的技巧，使它更有效但我无法想出任何。
在我看来，答案几乎总是一整个字符列表：所有使用过零次的字符。
更新
这可能是Java中最高效的。 为方便起见，我假设我们使用普通的Ascii。
public List rarest(String s) { int[] freq=new int[256]; for (int p=s.length()-1;p>=0;--p) { char c=s.charAt(p); if (c>255) throw new UnexpectedDataException("Wasn't expecting that"); ++freq[c]; } int min=Integer.MAX_VALUE; for (int x=freq.length-1;x>=0;--x) { // I'm assuming we don't want chars with frequency of zero if (freq[x]>0 && min>freq[x]) min=freq[x]; } List rares=new ArrayList (); for (int x=freq.length-1;x>=0;--x) { if (freq[x]==min) rares.add((char)x); } return rares; }
任何按照频率对列表进行排序的努力都会变得更加低效，因为每次检查一个字符时都必须重新排序。
任何对频率列表进行排序的尝试都会效率更低，因为对整个列表进行排序显然要比选择最小值慢。
排序字符串然后计数会变慢，因为排序将比计数更昂贵。
从技术上讲，在最后创建一个简单的数组而不是ArrayList会更快，但ArrayList会使代码更易读。
可能有一种方法可以更快地完成，但我怀疑这是接近最佳解决方案。 我当然有兴趣看看有没有更好的主意。
我认为你的方法在理论上是最有效的（O（n））。 然而在实践中它需要相当多的内存，并且可能非常慢。
它可能更有效（至少它使用更少的内存）将字符串转换为char数组，对数组进行排序，然后使用简单的循环计算频率。 但是，理论上由于排序效率较低（O（n log n））（除非您使用更有效的排序算法）。
测试用例：
import java.util.Arrays; public class Test { public static void main(String... args) throws Exception { // System.out.println(getLowFrequencyChar("x")); // System.out.println(getLowFrequencyChar("bab")); // System.out.println(getLowFrequencyChar("babaa")); for (int i = 0; i < 5; i++) { long start = System.currentTimeMillis(); for (int j = 0; j < 1000000; j++) { getLowFrequencyChar("long start = System.currentTimeMillis();"); } System.out.println(System.currentTimeMillis() - start); } } private static char getLowFrequencyChar(String string) { int len = string.length(); if (len == 0) { return 0; } else if (len == 1) { return string.charAt(0); } char[] chars = string.toCharArray(); Arrays.sort(chars); int low = Integer.MAX_VALUE, f = 1; char last = chars[0], x = 0; for (int i = 1; i < len; i++) { char c = chars[i]; if (c != last) { if (f < low) { if (f == 1) { return last; } low = f; x = last; } last = c; f = 1; } else { f++; } } if (f < low) { x = last; } return (char) x; } }
在字符串中查找字符频率的过程非常简单。
要回答，请参阅我的代码。
import java.io.*; public class frequency_of_char { public static void main(String args[])throws IOException { BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); int ci,i,j,k,l;l=0; String str,str1; char c,ch; System.out.println("Enter your String"); str=in.readLine(); i=str.length(); for(c='A';c<='z';c++) { k=0; for(j=0;j0) System.out.println("The character "+c+" has occured for "+k+" times"); } } }
我会按照以下方式执行此操作，因为它涉及最少的代码行：
你希望知道频率的字符：“_”
字符串“this_is_a_test”
String testStr = "this_is_a_test"; String[] parts = testStr.split("_"); //note you need to use regular expressions here int freq = parts.length -1;
如果字符串以相关字符开头或结尾，您可能会发现奇怪的事情，但我会留给您测试。
必须遍历HashMap并不一定是坏事。 那只是O(h) ，其中h是HashMap的长度 – 唯一字符的数量 – 在这种情况下总是小于或等于n 。 对于示例"aaabbc" ，对于三个唯一字符， h = 3 。 但是，由于h严格小于可能的字符数：255，因此它是常量。 所以，你的大哦将是O(n+h) ，实际上是O(n)因为h是常数。 我不知道任何算法可以获得更好的大哦 – 你可以尝试进行一堆特定于Java的优化，但是这里说的是我写的一个简单的算法，它找到频率最低的char 。 它从输入"aaabbc"返回"c" "aaabbc" 。
import java.util.HashMap; import java.util.Map; public class StackOverflowQuestion { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("" + findLowestFrequency("aaabbc")); } public static char findLowestFrequency(String input) { Map map = new HashMap(); for (char c : input.toCharArray()) if (map.containsKey(c)) map.put(c, map.get(c) + 1); else map.put(c, 0); char rarest = map.keySet().iterator().next(); for (char c : map.keySet()) if (map.get(c) < map.get(rarest)) rarest = c; return rarest; } }