Ранг решения строки

Question

У меня был вопрос, где он просит вас найти ранг строки среди ее перестановок, отсортированных по лексикографическому признаку.

O (N ^ 2) довольно ясно.

Некоторые веб-сайты также имеют решение O (n) . Оптимизированная часть в основном предварительно заполняет count array таким образом, что

count [i] содержит количество символов, которые присутствуют в str и меньше, чем i.

Я понимаю, что это уменьшит сложность, но не могу понять, как мы вычисляем этот массив. Это функция, которая делает это (взято из ссылки):

// Construct a count array where value at every index
// contains count of smaller characters in whole string
void populateAndIncreaseCount (int* count, char* str)
{
    int i;

    for( i = 0; str[i]; ++i )
        ++count[ str[i] ];

    for( i = 1; i < 256; ++i )
        count[i] += count[i-1];
}

Может ли кто-нибудь дать интуитивное объяснение этой функции?

Answer 1

Понял после повторного прохождения. Запутался из-за неправильного синтаксиса в c ++. Это на самом деле делает довольно простую вещь (Вот версия Java:

void populateAndIncreaseCount(int[] count, String str) {
    // count is initialized to zero for all indices
    for (int i = 0; i < str.length(); ++i) {
      count[str.charAt(i)]++;
    }

    for (int i = 1; i < 256; ++i)
      count[i] += count[i - 1];
  } 

После первого шага индексы, символы которых присутствуют в строке, отличны от нуля. Затем для каждого индекса в массиве count это будет сумма всех значений до index-1, поскольку массив представляет собой лексикографически отсортированные символы. И после каждого поиска мы также обновляем массив count:

// Удаляет символ ch из массива count [] // построено с помощью populateAndIncreaseCount ()

void updatecount (int* count, char ch)
{
    int i;
    for( i = ch; i < MAX_CHAR; ++i )
        --count[i];
}

Answer 2

Это решение выполняет Bucket Sort и затем сортирует выходные данные.

Сортировка сегмента O(items + number_of_possible_distinct_inputs), которая для фиксированного алфавита может быть объявлена ​​как O(n).

Однако на практике UTF создает довольно большой алфавит. Поэтому я бы предложил вместо этого быструю сортировку. Потому что быстрая сортировка, которая делится на три сегмента <, > и =, эффективна для большого набора символов, но все же использует преимущество маленького.