所以因为我被分配做一个问题来查找字符串中字符的频率 这是极客的例子,但我不明白它在做什么?所以我需要有人帮我解释。
Input : geeksforgeeks
Output :
Number of Occurrence of g is:2
Number of Occurrence of e is:4
Number of Occurrence of k is:2
Number of Occurrence of s is:2
Number of Occurrence of f is:1
Number of Occurrence of o is:1
Number of Occurrence of r is:1
这是代码
class NoOfOccurenceOfCharacters {
static final int MAX_CHAR = 256;
static void getOccuringChar(String str)
{
// Create an array of size 256 i.e. ASCII_SIZE
int count[] = new int[MAX_CHAR];
int len = str.length();
// Initialize count array index
for (int i = 0; i < len; i++)
count[str.charAt(i)]++;
// Create an array of given String size
char ch[] = new char[str.length()];
for (int i = 0; i < len; i++) {
ch[i] = str.charAt(i);
int find = 0;
for (int j = 0; j <= i; j++) {
// If any matches found
if (str.charAt(i) == ch[j])
find++;
}
if (find == 1)
System.out.println("Number of Occurrence of " +
str.charAt(i) + " is:" + count[str.charAt(i)]);
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String str = "geeksforgeeks";
getOccuringChar(str);
}
}
输出
Number of Occurrence of g is:2
Number of Occurrence of e is:4
Number of Occurrence of k is:2
Number of Occurrence of s is:2
Number of Occurrence of f is:1
Number of Occurrence of o is:1
Number of Occurrence of r is:1
count[str.charAt(i)]++
实际上做了什么? 我对这部分感到困惑,请有人向我解释一下吗?
为什么会有find = 0
?
嗯,count
是一个有256个插槽的int[]
:
int count[] = new int[MAX_CHAR]; // MAX_CHAR is 256
您的算法定义了MAX_CHAR = 256
,因为它假定字符串仅由 8 位 ASCII 字符组成。
[0, 0, ..., 0, 0] // 256 slots
现在,您正在迭代字符串str
中的每个字符并将其转换为整数(请参阅 Java 中基元的类型转换(。A
将转换为 65(ASCII 表(,B
转换为 66,依此类推。转换的int
是要递增的槽。因此,字符串A
将导致索引 65 处的整数递增。你的问题主要是关于
count[str.charAt(i)]++
这意味着:
char c = str.charAt(i); // c = A
int index = c; // c = A, casted to an int = 65
count[index]++ // increments the int at position 65
结果:
[0, 0, ..., 1, ..., 0, 0]
^ index 65
下一个A
将再次增加索引 65 处的 int:
[0, 0, ..., 2, ..., 0, 0]
^ index 65
使用HashMap
以String
存储字符和频率 循环遍历String
中的每个字符
例如:
(charCount.containsKey(arr1[i])) {
charCount.put(arr1[i], charCount.get(arr1[i]) + 1);
因此,count[str.charAt(i)]++
包括许多不同的阶段,可以简化如下以更好地理解:
char currentChar = str.charAt(i); // getting the current char to in the string
int value = count[currentChar]; // Get the current counter value
value = value + 1; // Increasing the current appearnce of this character by one
count[currentChar] = value; // Update the counter value
基本上,您的代码假设您正在使用 ASCII 字符串(可能包含 255 个不同的字符(并计算每个字符。
看起来预期的目标是按照重复字符在给定字符串中首次出现的顺序打印出来。 为了做到这一点,我们从左到右逐步str
for (int i=0; i < len; ++i) {
数组ch
,长度与str
相同,用于跟踪我们到目前为止已经检查过的str
的字符:
ch[i] = str.charAt(i);
接下来,我们计算字符str.charAt(i)
在ch[0]
中出现的次数..ch[i]
,以find
累积计数:
int find = 0;
//...
for (int j = 0; j <= i; j++) {
if (str.charAt(i) == ch[j])
find++;
}
如果find == 1
,这意味着我们是第一次遇到角色str.charAt(i)
,我们应该打印出它的频率:
if (find == 1)
System.out.println("Number of Occurrence of " +
str.charAt(i) + " is:" + count[str.charAt(i)]);
}
请注意,在任何给定时刻,ch[0]
中的字符..ch[i]
与str.charAt(0)
字符完全相同..str.charAt(i)
,所以额外的ch
数组并不是真正必要的。 我们可以直接在str
的前i
个字符中计算str.charAt(i)
的出现次数,如下所示:
for (int i = 0; i < str.length(); ++i){
int find = 0;
for (int j = 0; j <= i; ++j) {
if (str.charAt(j) == str.charAt(i))
++find;
}
if (find == 1)
System.out.println("Number of Occurrence of " +
str.charAt(i) + " is:" + count[str.charAt(i)]);
}
另一种方法是不需要重新叙述字符的方法,前提是一旦显示字符,您就不再需要频率计数。 您可以使用频率计数来跟踪哪些字符的频率已经打印,哪些字符的频率尚未打印,方法是 1( 在打印后将频率计数归零,2( 仅打印频率为非零的字符:
for (int i = 0; i < str.length(); ++i) {
if (count[str.charAt(i) > 0) {
System.out.println("Number of Occurrence of " +
str.charAt(i) + " is:" + count[str.charAt(i)]);
count[str.charAt(i)] = 0;
}
}
优化方式
import java.util.ArrayList;
import java.util.List;
public class HelloWorld{
static final int MAX_CHAR = 256;
static List<Character> sequence = new ArrayList<>();
static void getOccuringChar(String s){
int count[] = new int[MAX_CHAR];
for(int i=0;i<s.length();i++){
count[s.charAt(i)]++;
if(!sequence.contains(s.charAt(i)))
sequence.add(s.charAt(i));
}
for(int i=0;i<sequence.size();i++)
System.out.println("Number of Occurrence of "+sequence.get(i)+" is:"+count[sequence.get(i)]);
}
public static void main(String arg[]){
getOccuringChar("geeksforgeeks");
}
}
输出为
Number of Occurrence of g is:2
Number of Occurrence of e is:4
Number of Occurrence of k is:2
Number of Occurrence of s is:2
Number of Occurrence of f is:1
Number of Occurrence of o is:1
Number of Occurrence of r is:1