问理解字符串算法中的“查找最大出现字符”
EN

Stack Overflow用户

提问于 2020-12-07 02:59:52

回答 2查看 403关注 0票数 3

我正在学习数据结构和算法，我有一个小问题，就是如何理解在字符串中发现哪一个字符最多的过程。

我理解总体目标--拥有一个表示特定字符计数的数组，我显然了解如何在数组中找到max，但我对这一堆代码(来自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

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

count["t"]++

所以它基本上告诉我“给我索引的值”，我怎么能用字符搜索，我应该用索引搜索？

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

我可能错过了妨碍我理解这一点的基本概念，但经过简短的谷歌搜索后，我没有找到多少。

ascii

java

arrays

algorithm

kotlin

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-12-07 03:23:12

Java将将char转换为int，例如，根据ASCII表将'A‘转换为65。

只要您的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'，即使它很简单，但它非常适合当前的问题，因为它唯一地将给定的字符映射到数组上的某个位置。

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

数"t“++，所以它基本上告诉我”给我索引的值“？我怎么能用字符搜索，我应该在哪里搜索索引？

请注意，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

票数 4

Stack Overflow用户

发布于 2020-12-07 03:25:10

基本上，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;