java - 以高性能的方式计算字符串中出现的字符？‽？

问题描述

我正在做以下编程练习：字符串的数值。声明是：

您将获得一个输入字符串。

对于字符串中的每个符号，如果它是第一个出现的字符，请将其替换为“1”，否则将其替换为您已经看到它的次数...

但是您的代码是否足够高效？例子：
input   =  "Hello, World!"
result  =  "1112111121311"

input   =  "aaaaaaaaaaaa"
result  =  "123456789101112"
字符串中可能有一些非 ASCII 字符。

注意：不会有 int 域溢出（字符出现少于 20 亿）。

我写了以下答案：

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]

我们如何改进解决方案？哪种算法能更好地处理非常大的输入字符串？为了改进这个答案，我们应该调试和避免的瓶颈在哪里？

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

编辑：这里我们有一个基于@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();
  }
}

标签： javastringalgorithmperformancechar

我认为你在正确的轨道上使用 a Map，但你的 key 类型应该是Character和你的 count 类型Integer。我认为当您对结果进行反转和排序时，您出错了。此外，如果没有流，您的代码会更容易阅读（编写快速代码的关键部分是编写哑代码）。例如，

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

java - 以高性能的方式计算字符串中出现的字符？‽？

问题描述

解决方案

推荐阅读