理解字符串算法中的"find maximum occuring char"

Question

我正在学习数据结构和算法，但在理解查找字符串中出现次数最多的字符的过程时遇到了一个小问题。

我理解总体目标——拥有一个表示特定字符计数的数组，我显然理解如何在数组中找到最大值，但我对这段代码有很大的疑问（代码来自 https://www.geeksforgeeks.org/return-maximum-occurring-character-in-the-input-string/):

        int count[] = new int[256]; 

          for (int i=0; i<str.length(); i++) 
            count[str.charAt(i)]++; <-- what I don't understand

我正在初始化计数数组以保存整数，但在 for 循环内我正在搜索字符串中的特定字符，例如：

count["t"]++

所以它基本上是在告诉我“给我索引“t”的值？我怎么能用字符搜索我应该用索引搜索的地方呢？

同样在 kotlin 中，我得到预期 (count[str.get(i)]) 它期待 int，而不是 char。

我可能错过了阻止我理解这一点的基本概念，但经过短暂的 google 搜索，我没有找到太多东西。

Answer 1

Java 会根据 ASCII [=] 将 char 转换为 int，例如 'A' 到 65 65=].

只要您的 string 不包含 return 值大于 255 的字符（例如， "€")，256 个位置的数组足以将可能的 chars 映射到数组位置。例如，对于英文字母，这就足够了。尽管如此，由于 Java 中的字符是 2 bytes（16 位），因此 65536 (2^16) 大小的数组足以安全。您还可以根据该字符串上存在的所有字符计算 max int 值（假设为非空或空字符串）并相应地分配数组：

int count[] = new int[str.chars().max().orElse(0)+1];

回到你的问题：

count[some_char]++

将some_char转换为int，并在相应的数组count位置增加一个值。

您可以将此过程视为将 'char' 映射到 'int' 的简单哈希函数，尽管它很简单，但它非常适合手头的问题，因为它唯一地映射了一个给定的char 到该数组的某个位置。

I'm initializing count array to hold ints, but inside the for loop I'm searhing for specific char in a string, so for example:

count["t"]++ So it basically telling me "give me the value of index "t"? how can I even search with chararter where I should search with index?

注意 count["t"]++ 会给你一个编译错误，函数 str.charAt(i) return 是 char，而不是 String，因此't' 而不是“t”。

一个运行例子：

import java.util.Arrays;
import java.util.stream.Collectors;

public class FindMaximumOccurringChar {

    private static int[] countChar(String str) {
        int[] count = new int[str.chars().max().orElse(0) + 1];
        for (int i = 0; i< str.length(); i++)
            count[str.charAt(i)]++;
        return count;
    }

    public static void main(String[] args) {
        String str = "miaumiauuuuu";
        int[] count = countChar(str);
        String str_without_duplicated_char = Arrays.stream(str.split(""))
                .distinct()
                .collect(Collectors.joining());

        for (int i=0; i<str_without_duplicated_char.length(); i++){
            System.out.println("The char '"+str_without_duplicated_char.charAt(i)+"' shows up "
                    + count[str_without_duplicated_char.charAt(i)] +" times");
        }
    }
}

输出：

The char 'm' shows up 2 times
The char 'i' shows up 2 times
The char 'a' shows up 2 times
The char 'u' shows up 6 times

Answer 2

基本上，count[str.charAt(i)]++，存储输入字符串中每个字符的计数。 Java 将每个字符索引转换为 ASCII 值。

let say str = "abca";

For each iteration : 
count['a'] = 1; or count[97] = 1;  a has ascii value 97
count['b'] = 1; or count[98] = 1;  b has ascii value 98
count['c'] = 1; or count[99] = 1;  c has ascii value 99
count['a'] = 2; or count[97] = 2;

理解字符串算法中的"find maximum occuring char"

Understand "find maximum occuring char" in a string algorithm

java

arrays

algorithm

ascii

kotlin