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

在最近的一次采访中，我被要求编写以下程序。 找出给定字符串中频率最小的字符？ 因此，我尝试使用 charAt 迭代字符串，并将字符存储为 HashMap 中的键，并将出现次数作为其值。 现在我必须再次迭代 Map 才能找到最低的元素。

有没有一种更有效的方法来做到这一点，因为我想显然上面的方法太密集了。

更新和另一个解决方案

经过一些思考过程和答案后，我认为最好的时间是 O(n)。 在第一次迭代中，我们必须逐个字符地遍历字符串，然后将它们的频率存储在数组中的特定位置（字符是整数），同时有两个临时变量来维护最小计数和相应的字符。因此，当我转到下一个字符并将其频率存储在 arr[char] = arr[char]+1 中时；同时我将检查临时变量的值是否大于该值，如果是，则临时变量将是这个值，并且字符也将是这个。通过这种方式，我想我们不需要第二次迭代来找到最小的，而且我猜也不需要排序

....说什么？或者还有什么解决方案

我会使用数组而不是哈希图。如果仅限于 ascii，则只有 256 个条目；如果我们使用 Unicode，则为 64k。无论哪种方式，都不是不可能的尺寸。除此之外，我不知道你可以如何改进你的方法。我试图想出一些巧妙的技巧来提高效率，但我想不出任何办法。

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

Update

这可能是最接近 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 使代码的可读性稍微好一些。

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