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

Question

我收到超过时间限制？

类似 Char 问题描述 Tahir 和 Mamta 正在 TCS 中的一个项目中工作。Tahir 是一个问题解决者，他为他的朋友 Mamta 想出了一个有趣的问题。

问题由一个长度为 N 的字符串组成，并且只包含小写字母。

接下来是 Q 个查询，其中每个查询将包含一个整数 P (1<=P<=N)，表示字符串中的一个位置。

Mamta 的任务是找到该位置出现的字母表，并确定给定位置 P 之前相同字母表的出现次数。

Mamta 正忙于她的办公室工作。因此，她请求你帮助她。

约束 1 <= N <= 500000

S 由小写字母组成

1 <= Q <= 10000

1 <= P <= N

输入格式 第一行有一个整数N，表示字符串的长度。

第二行包含字符串 S 本身仅包含小写字母 ('a' - 'z')。

第三行包含一个整数 Q，表示将被询问的查询数。

接下来的 Q 行包含一个整数 P (1 <= P <= N)，您需要为此查找 P 之前第 P 个位置出现的字符的出现次数。

输出 对于每个查询，在单行上打印一个表示答案的整数。

测试用例

说明例1

输入

9

算盘

2

9

3

输出

3

1

解释

这里 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&nbsp;k=0;k<s.substring(0,qq-1).length();k++){ &nbsp;&nbsp;if((s.substring(0,(qq-1)).charAt(k)==someChar))&nbsp;count[j]++; }让我们看几个方面：k<s.substring(0,qq-1).length()创建一个子字符串，以便它可以计算出它的长度。但是我们知道那个长度是多少：&nbsp;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&nbsp;*&nbsp;q)降低到O(s + q&nbsp;*&nbsp;log(s))。如果您不知道二进制搜索，请查找它。或者使用 aMap<Integer, Integer>而不是数组或列表。更高效的是，构建一个与字符串长度相同的数组，并在每个索引中存储关于该索引的查询的答案。我相信这可以用复杂度O(s + q)来实现。