CODEVITA "подобный символ" как уменьшить мою временную сложность в c?

Question

Пример 1

Ввод

9

abacsddaa

2

9

3

Вывод

3

1

Пояснение

Здесь Q = 2

Для P = 9 символ в 9-м месте это'. Число вхождений 'a' перед P, т. Е. 9 равно 3.

Аналогично для P = 3, третий символ - 'a'. Число вхождений 'a' перед P. т. Е. 3 равно 1.

Мой ответ:

#include<stdio.h>
#include<stdlib.h>

int occ(int a,char *p){
  int cnt=0;
  for(int i=0;i<a;i++){
    if(p[i]==p[a]){
      cnt++;
    }
  }

  return cnt;
}

int main(){
  int l,q;

  scanf("%d",&l);
  char s[l];
  scanf("\n%s\n%d",s,&q);
  while(q>0){
    int n;
    scanf("\n%d",&n);
    n=n-1;
    int r=occ(n,s);
    printf("%d\n",r);
    q--;
  }
}

Answer 1

Я не эксперт C, но я могу дать вам представление о том, как улучшить вашу временную сложность здесь.

Вы можете использовать своего рода запоминание, сначала спросите: есть ли что-нибудь полезное информацию, которую я могу получить от итерации массива только один раз, чтобы я мог быстрее отвечать на каждый запрос?

Сейчас ваше решение ничего не обрабатывает заранее, а ваша сложность составляет O (n) на запрос. Давайте сделаем что-нибудь лучше, давайте предварительно обработаем данные в O (n) и ответим на каждый запрос в O (1).

У вас будет карта символов, которая будет подсчитывать, сколько раз появляется символ. Обратите внимание, что для индекса i вы просто учитываете появление s [i] раньше, поэтому индекс i не заботится о других символах.

Следуйте этому подходу

1. Создайте vector (int) v размера s.length.
2. Создайте карту (char to int) m для подсчета появления символов.

3. Для i = 0 до s.length выполните:

    v[i] = m[s[i]]++
   

Таким образом, вы просто вычислили ответ для каждого индекса за одну итерацию.

Теперь для каждого запроса q просто выведите v [q - 1 ].

Временная сложность на запрос: O (1)

Сложность дополнительного пространства: O (n)

Примечание. Для лучшего понимания всего ответа n - это длина строки (s.length)

Надеюсь, что это поможет :)

Answer 2

Текущая сложность выполнения составляет O (lq) , где l - длина входного массива, а q - количество запросов.

Сложность каждого запроса составляет O (l) .

При правильной структуре данных вы можете сохранить входные данные таким образом, чтобы каждый запрос был O (1 ) . Например, вы можете создать таблицу, в которой каждая строка будет представлять букву (от a до z, для этого примера предположим, что мы получаем только строчные буквы). В каждом столбце будет указано количество раз, когда данная буква встречалась до (включительно) индекса этого столбца.

Например, если введено aabz, таблица будет выглядеть так:

   | 0    1    2    3
------------------------
 a | 1    2    2    2
 b | 0    0    1    1
 . | .    .    .    .
 . | .    .    .    .
 y | 0    0    0    0
 z | 0    0    0    1

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

1. Проверить букву по индексу 2 во входной строке ('b')
2. Проверьте значение в таблице поиска на ['b'] [2] -> 1

Сложность для создать такую ​​таблицу будет O (l) . Вот пример кода для построения такой таблицы:

#define CHARS_SIZE ('z' - 'a' + 1)

// 'arr' - is the input array of chars
// 'len' - length of the input array
// 'lookup' - pointer to a zeroed (cleared) array of size: CHARS_SIZE * len * sizeof(*lookup)
void build_lookup(const char *arr, int len, int *lookup)
{
    int char_val;

    // normalize the letter to integer value between 0 (for 'a') and 25 (for 'z')
    char_val = arr[0] - 'a';
    lookup[char_val*len] = 1;

    // 'i' indicates the column index in the table
    for (int i = 1; i < len; ++i)
    {
        char_val = arr[i] - 'a';
        // update the number of occurrences for each letter a..z at column 'i'
        for (int char_iter = 0; char_iter < CHARS_SIZE; ++char_iter)
        {
            if (char_iter != char_val)
            {
                // same value as the previous one
                lookup[char_iter*len + i] = lookup[char_iter*len + i - 1];
            }
            else {
                // +1 to the value in the previous value
                lookup[char_iter*len + i] = lookup[char_iter*len + i - 1] + 1;
            }
        }
    }
}

Запрос в таком случае будет:

int occ(const char *arr, int len, const int *lookup, int idx){
    // normalize the letter to integer value between 0 (for 'a') and 25 (for 'z')
    int char_val = arr[idx] - 'a';

    return lookup[char_val * len + idx];
}

Вот ваш код с небольшими добавлениями того, что я объяснено выше: https://godbolt.org/z/zaY4RL

Обратите внимание, что я не тестировал его, поэтому, вероятно, есть несколько ошибок, поэтому используйте его как ссылку, а не как полное решение.