Warm tip: This article is reproduced from serverfault.com, please click

java-了解字符串算法中的“查找最大出现的字符”

(java - Understand "find maximum occuring char" in a string algorithm)

发布于 2020-12-07 10:59:52

我正在学习数据结构和算法,但在理解查找字符串中哪个字符最多的过程方面遇到了一个小问题。

我了解总体目标-具有代表特定字符计数的数组,我显然了解如何在数组中找到max,但是我对这个代码夹头有很大的疑问(来自https://www.geeksforgeeks.org的代码/在输入字符串中返回最大出现的字符/):

        int count[] = new int[256]; 

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

我正在初始化count数组以容纳int,但是在for循环中,我正在搜索字符串中的特定char,例如:

count["t"]++

因此,它基本上告诉我“给我索引t的值?”我该如何甚至在应该使用索引进行搜索的chararter中进行搜索?

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

我可能错过了使我无法理解的基本概念,但是经过简短的Google搜索后,我发现的内容并不多。

Questioner
Masksway
Viewed
0
dreamcrash 2021-02-21 04:49:26

Java会根据该将转换charint,例如'A' 65ASCII

在此处输入图片说明

只要你string不包含返回值大于255例如 "€"的字符,256位置数组就足以将可能的值映射chars到数组位置。例如,对于英文字母来说,就足够了。不过,由于Java中的char是2 bytes(16位),因此大小为65536(2 ^ 16)的数组足以保证安全你还可以根据该max int字符串上存在的所有字符(假定为非null或空字符串)来计算值,并相应地分配数组:

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

返回你的问题:

count[some_char]++

转换some_charint,并在对应的数组count位置上增加一个值

你可以将这个过程视为一个简单的哈希函数,将“ char”映射到“ int”,尽管它很简单,但由于它将给定char唯一地映射到该数组上的某个位置,因此它非常适合当前的问题。

我正在初始化count数组以容纳int,但是在for循环中,我正在搜索字符串中的特定char,例如:

count [“ t”] ++因此,它基本上告诉我“给我索引t的值?”我该如何甚至在chararter中搜索应该在索引中进行搜索的地方?

请注意,count["t"]++这会给你带来编译错误,该函数str.charAt(i)将返回a char,而不是a 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