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

Question

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

是否有更有效的方法来做到这一点，显然我认为上述方法过于密集。

更新和另一个解决方案

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

.... 怎么说？或者更多解决方案

Answer 1

我会使用数组而不是 HashMap 。如果我们仅限于 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 使代码的可读性稍微好一些。

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