在java中查找字符串中字符频率的有效方法：O（n）

Question

在最近的一次采访中，我被要求写以下节目。 找出给定字符串中频率最小的字符？ 因此，我尝试使用charAt遍历字符串，并将该字符作为键存储在HashMap中，将出现次数作为其值。 现在我必须在地图上迭代，找到最低的元素

有没有更有效的方法来做这件事，因为我想上面的方法显然太密集了

更新和其他解决方案

经过一些思考和回答后，我认为最好的时间是O（n）。 在第一次迭代中，我们必须逐个字符迭代字符串，然后将它们的频率存储在特定位置的数组中（字符是int），同时有两个临时变量，它们保持最少的计数和相应的字符。因此，当我转到下一个字符并将其频率存储在arr[char]=arr[char]+1中时；同时，我会检查温度变量是否有一个大于这个值的值，如果是，那么温度变量将是这个值，字符也将是这个值。这样的话，我想我们不需要第二次迭代来找到最小的，也不需要排序

。。。。怎么说？还有其他解决方案吗

Answer 1

我认为你的方法在理论上是最有效的。然而在实践中，它需要相当多的内存，而且可能非常慢

将字符串转换为字符数组，对数组进行排序，然后使用一个简单的循环计算频率，可能会更高效（至少它使用更少的内存）。然而，在理论上，由于排序（除非使用更高效的排序算法），它的效率较低（O（n logn））

测试用例：

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

}

Answer 2

我会使用数组而不是哈希映射。如果我们仅限于ascii，那只有256个条目；如果我们使用的是Unicode，64k。不管怎样都不是不可能的尺寸。除此之外，我不认为你可以改进你的方法。我正试图想出一些聪明的办法来提高效率，但我想不出任何办法

在我看来，答案几乎总是一个完整的字符列表：所有那些被零次使用的字符

更新

在Java中，这可能是最高效的。为了方便起见，我假设我们使用的是普通Ascii码

public List<Character> 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<Character> rares=new ArrayList<Character>();
  for (int x=freq.length-1;x>=0;--x)
  {
    if (freq[x]==min)
      rares.add((char)x);
  }
  return rares;
}

任何在执行时按频率对列表进行排序的努力都会变得更加低效，因为每次检查一个字符时，它都必须重新排序

任何对频率列表进行排序的尝试都将更加低效，因为对整个列表进行排序显然比只选择最小值要慢

对字符串进行排序，然后再进行计数的速度会较慢，因为排序的成本会高于计数

从技术上讲，在最后创建一个简单的数组比创建ArrayList要快，但ArrayList生成的代码可读性稍高一些

也许有一种方法可以更快地完成，但我怀疑这接近最佳解决方案。我当然有兴趣看看是否有人有更好的主意

Answer 3

必须遍历HashMap并不一定是坏事。这只会是O(h)，其中h是HashMap的长度——唯一字符的数量——在本例中，它总是小于或等于n。例如"aaabbc"，h = 3表示三个唯一的字符。但是，因为h严格小于可能的字符数：255，所以它是常量。所以，你的大oh是O(n+h)，实际上是O(n)，因为h是常数。我不知道有哪种算法能得到更好的结果。哦，你可以尝试进行一些特定于java的优化，但这就是我写的一个简单算法，它可以找到频率最低的char。它从输入"aaabbc"返回"c"

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<Character, Integer> map = new HashMap<Character, Integer>();

    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;

}

}