Как оптимизировать этот код, чтобы сэкономить время выполнения?

Код следующий. Я думаю, что метод сортировки занимает больше времени.
поэтому при необходимости измените код.
Первая строка входных данных содержит два целых числа, разделенных пробелами, N (количество символов в строке) и Q (общее количество запросов), соответственно.

Вторая строка входных данных содержит строку S.

Каждая из следующих Q строк содержит запрос . Запрос является одним из следующих двух типов:

  • 1 X C-запрос имеет тип 1, символ в позиции X (целое число) в строке должен быть заменен на C (символ).
  • 2 X-запрос типа 2, выведите символ, который будет присутствовать в позиции X (целое число) в строке, если символы в строке расположены в алфавитном порядке.

ВЫХОД:

Для каждого запроса типа 2 выведите символ, находящийся в позиции X, если символы в строке расположены в алфавитном порядке.

import java.util.*;

public class test{

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        int N=scan.nextInt();
        int n=scan.nextInt();
        String S=scan.next();
        char[]chars=S.toCharArray();
        Arrays.sort(chars);

        StringBuilder sb=new StringBuilder(S);

        for(int i=0;i<n;i++){

            int b=scan.nextInt();
            if(b==1){
                int c=scan.nextInt();
                char c1=scan.next().charAt(0);
                sb.setCharAt(c-1, c1);
                String newString=sb.toString();
                chars=newString.toCharArray();
                Arrays.sort(chars);
            }

            if (b==2){

                int c=scan.nextInt();
                System.out.println(chars[c-1]);
            }

        }

1 ответ

  1. Я предполагаю, что вы хотите сократить время выполнения. Вам нужно только держать две копии исходного текста, в настоящее время у вас есть Stringa StringBuilderи a char[]. Я бы предложил сохранить только два из них: A char[]с исходным порядком, измененным запросами типа 1, и второй char[]с отсортированными символами для ответа на запросы типа 2.

    Сортировка символов после каждого запроса типа 1. В этом нет необходимости. Если запрос типа 2 следует за запросом типа 1 (или является первым), то необходимо использовать сортированный массив. В противном случае сортировка будет потеряна. Это сэкономит вам некоторые виды, Если вы не уверены, что каждый тип 2 всегда следует за типом 1. Сортировка, безусловно, теряется, если два или более типа 1 следуют друг за другом.