java - 以一种高效的方式计算字符串中出现的字符？‽？

Question

我正在做以下编程练习: Numericals of a String 。声明是:

You are given an input string.

For each symbol in the string if it's the first character occurence, replace it with a '1', else replace it with the amount of times you've already seen it...

But will your code be performant enough? Examples:

input   =  "Hello, World!"
result  =  "1112111121311"

input   =  "aaaaaaaaaaaa"
result  =  "123456789101112"

There might be some non-ascii characters in the string.

Note: there will be no int domain overflow (character occurences will be less than 2 billion).

我写了以下答案:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    System.out.println("ocurrences: "+ocurrences.toString());                                    
    StringBuilder result = new StringBuilder();                                    
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result.append(ocurrences.get(c) + " ");
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+result.toString());
    String[] chars = result.toString().split(" ");
    Collections.reverse(Arrays.asList(chars));
    String sorted = String.join("",chars);
    System.out.println("sorted: "+sorted);
    return sorted;
  }
}

但是，当输入字符串很大时，它会超时(执行时间超过 16000 毫秒)。

要查看它是如何工作的，有一个带有非常小的输入字符串的跟踪:

s: Hello, World!
result: 1 1 3 1 2 1 1 1 1 2 1 1 1 
sorted: 1112111121311

此外，我还写了以下替代答案:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    String[] result = new String[s.length()];                                   
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result[i] = String.valueOf(ocurrences.get(c));
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+Arrays.toString(result));
    return String.join("",result);
  }
}

即便如此，它仍然超时。

这是一个带有小输入字符串的跟踪:

s: Hello, World!
result: [1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 1]

我们如何改进解决方案？什么算法的性能足以处理非常大的输入字符串？我们应该调试和避免的瓶颈在哪里，以改进这个答案？

为了尝试自己解决它，我已阅读:

How do I count the number of occurrences of a char in a String?

Hashmap implementation to count the occurrences of each character

How do I reverse an int array in Java?

https://www.codewars.com/kata/5b4070144d7d8bbfe7000001/discuss

HashMap to return default value for non-found keys?

What is the difference between putIfAbsent and computeIfAbsent in Java 8 Map ?

编辑:这里我们有一个基于@khelwood 建议的答案:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals/*🔡->🔟*/(String s) {
    Map<String, Integer> ocurrences = new HashMap<String,Integer>();
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < s.length(); i++){
      String c = String.valueOf(s.charAt(i));
      ocurrences.putIfAbsent(c, 0);
      ocurrences.put(c,ocurrences.get(c)+1);
      result.append(ocurrences.get(c));
    }
    return result.toString();
  }
}

Answer 1

我认为您使用 Map 走在正确的轨道上，但您的 key 类型应该是 Character ，而您的计数类型应该是 Integer 。我认为当你反转并排序你的结果时你错了。此外，如果没有流，您的代码会更容易阅读(编写快速代码的关键部分是 write dumb code )。例如，

public static String numericals(String s) {
    int len = s.length();
    Map<Character, Integer> occurrences = new HashMap<>(); // ocurrences
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        int count = occurrences.getOrDefault(ch, 0) + 1;
        occurrences.put(ch, count);
        sb.append(count);
    }
    return sb.toString();
}

然后测试一下

public static void main(String[] args) {
    String[] input = { "Hello, World!", "aaaaaaaaaaaa" };
    String[] output = { "1112111121311", "123456789101112" };
    for (int i = 0; i < input.length; i++) {
        String result = numericals(input[i]);
        System.out.printf("%s %b%n", result, result.equals(output[i]));
    }
}

哪些输出

1112111121311 true
123456789101112 true