有效的方式找到字符串中字符的频率在java：O（n） [英] Efficient way to find Frequency of a character in a String in java : O(n)

问题描述

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

有一个更有效的方法来做，显然上面的

$ b

更新和另一个解决方案

答案我认为最好的时间，这可以是O（n）。
在第一次迭代中，我们必须逐个字符地遍历字符串，然后将它们的频率存储在特定位置的一个数组中（字符是一个int），同时有两个临时变量保持最少计数，相应的字符。所以当我去下一个字符并存储它的频率在arr [char] = arr [char] +1;同时我将检查temp变量是否有一个大于此值，如果是那么临时变量将是这个值，并且字符将是这一个。这样，我想我们不需要第二次迭代找到最小，也不需要排序我想

.... Wat说？或任何其他解决方案

解决方案

我会使用数组而不是哈希映射。如果我们只限于ascii，那只有256个条目;如果我们使用Unicode，64k。任何一种方式不是不可能的大小。除此之外，我不知道你可以如何改进你的方法。我试图想出一些聪明的技巧，使它更有效率，但我不能想出任何。

看起来我的答案几乎总是去

$ b

b

这可能是最有效的，它可能在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 
 if（c> 255）
 throw new UnexpectedDataException（Was not expecting that）; 
 ++ freq [c]; 
} 
 int min = Integer.MAX_VALUE; 
 for（int x = freq.length-1; x> = 0;  -  x）
 {
 //我假设我们不需要频率为零的字符
 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只是稍微更可读的代码。 / p>

有一种方法可以做得更快，但我怀疑这是接近最佳的解决方案。我肯定会有兴趣看看有没有更好的主意。

In a recent interview I was asked to write the below program. Find out the character whose frequency is minimum in the given String ? So I tried by iterating through the string by using charAt and storing the character as key in a HashMap and the number of occurences as its value. Now Again I have to iterate on the Map to find the lowest element.

Is there a more efficient way to do it as obviously the above one is too intensive i guess.

Update and Another Solution

After some thought process and answers I think the best time that this can be is O(n). In the first iteration we will have to iterate through the String character by character and then store their frequency in an Array at the specific position(character is an int) and same time have two temporary variables which maintain the least count and the corresponding character.So when I go to the next character and store its frequency in arr[char] = arr[char]+1;At the same time I will check if the temp varible has a value greater than this value,if yes then the temp varible will be this value and also the char will be this one.In this way i suppose we dont need a second iteration to find the smallest and also no sorting is required I guess

.... Wat say ? Or any more solutions

解决方案

I'd use an array rather than a hash map. If we're limited to ascii, that's just 256 entries; if we're using Unicode, 64k. Either way not an impossible size. Besides that, I don't see how you could improve on your approach. I'm trying to think of some clever trick to make it more efficient but I can't come up with any.

Seems to me the answer is almost always going to be a whole list of characters: all of those that are used zero times.

Update

This is probably clost to the most efficient it could be in Java. For convenience, I'm assuming we're using plain 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;
}

Any effort to keep the list sorted by frequency as you go is going to be way more inefficient, because it will have to re-sort every time you examine one character.

Any attempt to sort the list of frequencies at all is going to be more inefficient, as sorting the whole list is clearly going to be slower than just picking the smallest value.

Sorting the string and then counting is going to be slower because the sort will be more expensive than the count.

Technically, it would be faster to create a simple array at the end rather than an ArrayList, but the ArrayList makes slightly more readable code.

There may be a way to do it faster, but I suspect this is close to the optimum solution. I'd certainly be interested to see if someone has a better idea.

这篇关于有效的方式找到字符串中字符的频率在java：O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！