为什么我会超过时间限制？

Question

我收到超过时间限制？类似 Char 问题描述 Tahir 和 Mamta 正在 TCS 中的一个项目中工作。Tahir 是一个问题解决者，他为他的朋友 Mamta 想出了一个有趣的问题。问题由一个长度为 N 的字符串组成，并且只包含小写字母。接下来是 Q 个查询，其中每个查询将包含一个整数 P (1<=P<=N)，表示字符串中的一个位置。Mamta 的任务是找到该位置出现的字母表，并确定给定位置 P 之前相同字母表的出现次数。Mamta 正忙于她的办公室工作。因此，她请求你帮助她。约束 1 <= N <= 500000S 由小写字母组成1 <= Q <= 100001 <= P <= N输入格式 第一行有一个整数N，表示字符串的长度。第二行包含字符串 S 本身仅包含小写字母 ('a' - 'z')。第三行包含一个整数 Q，表示将被询问的查询数。接下来的 Q 行包含一个整数 P (1 <= P <= N)，您需要为此查找 P 之前第 P 个位置出现的字符的出现次数。输出 对于每个查询，在单行上打印一个表示答案的整数。测试用例说明例1输入9算盘293输出31解释这里 Q = 2对于 P=9，第 9 个位置的字符是 'a'。P 之前'a' 的出现次数，即9 是3。类似地，对于 P=3，第 3 个字符是 'a'。P 之前'a' 的出现次数。即3 是一次。import java.io.*;public class simchar{    public static void main(String gg[]) throws Exception    {        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));        int n=Integer.parseInt(reader.readLine());        String s=reader.readLine();        if(s.length()!=n) return;        int q=Integer.parseInt(reader.readLine());        int qq;        int []count=new int[q];        char someChar;        for(int j=0;j<q;j++)        {            qq=Integer.parseInt(reader.readLine());            someChar=s.charAt(qq-1);            for(int k=0;k<s.substring(0,qq-1).length();k++){                if((s.substring(0,(qq-1)).charAt(k)==someChar)) count[j]++;            }            System.out.println(count[j]);        }        reader.close();    }}

Answer 1

除了奥莱的回答，你还需要考虑一些“微”优化：

我怀疑大部分时间都会花在执行这个循环上：

for(int k=0;k<s.substring(0,qq-1).length();k++){
  if((s.substring(0,(qq-1)).charAt(k)==someChar)) count[j]++;
}

让我们看几个方面：

• k<s.substring(0,qq-1).length()创建一个子字符串，以便它可以计算出它的长度。但是我们知道那个长度是多少： qq！qq因此，您无缘无故地创建了一个新字符串并复制了字符。效率低下。无意义。

• s.substring(0,(qq-1)).charAt(k)==someChar创建另一个字符串，然后获取它的k第 th 个字符。但是k子字符串的第 th 个字符也是k原始字符串的第 th 个字符s。（想想看！）所以，再一次创建子串是没有意义的。

• 那些不必要的计算都重复了qq多次。这是相同的（不必要的）计算完成2 x qq时间。

注意：此分析不考虑您的代码是否正确或算法是否最优。这纯粹是关于微观效率。你所做的是将O(N^2)算法变成O(N^3)算法......由于不必要的子字符串创建。

Answer 2

对于长字符串（最多 500000 个字母）和许多查询（最多 10000 个）的有效解决方案，您需要以某种方式预处理字符串数据，以便之后您可以快速处理每个查询。我建议对于 26 个可能的小写字母（问题明确表示“a”-“z”）中的每一个，找到第 1、2、3 次出现的位置等，并将它们填充到数组或列表中。然后对于每个查询，在数组中进行二进制搜索以查找您作为输入获得的位置。然后找到的数组索引会告诉你答案。这会将您的时间复杂度从O(s^2 * q)降低到O(s + q * log(s))。

如果您不知道二进制搜索，请查找它。或者使用 aMap<Integer, Integer>而不是数组或列表。

更高效的是，构建一个与字符串长度相同的数组，并在每个索引中存储关于该索引的查询的答案。我相信这可以用复杂度O(s + q)来实现。