查找java中字符串中字符频率的有效方法:O(n)

Question

在最近的一次采访中,我被要求写下面的程序.找出给定字符串中频率最小的字符？所以我尝试通过使用charAt迭代字符串并将字符作为键存储在HashMap中,并将出现次数作为其值.现在,我必须迭代Map以找到最低元素.

有没有一种更有效的方法来做到这一点,显然上面这个太强烈了我猜.

更新和另一种解决方案

经过一些思考过程和答案后,我认为最好的时间是O(n).在第一次迭代中,我们将不得不逐字符遍历字符串,然后将它们的频率存储在特定位置的数组中(字符是int),同时有两个临时变量,它们保持最少的计数和相应的字符.所以当我转到下一个字符并将其频率存储在arr [char] = arr [char] +1中;同时我将检查temp varible是否具有大于此值的值,如果是,那么temp变量将是这个值,并且char也将是这一个.这样我想我们不需要第二次迭代来找到最小的并且也不需要排序我猜

.... Wat说？或者更多解决方案

Answer 1

我使用数组而不是哈希映射.如果我们仅限于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会使代码更易读.

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