java - 理解字符串算法中的 "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。

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

Answer 1

Java 将转换 char进入 int ，例如，“A”到 65根据ASCII表。

只要您的string不包含返回值大于 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”的简单哈希函数，尽管它很简单，但它完全适合手头的问题，因为它将给定的字符唯一地映射到其上的某个位置数组。

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)给你一个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