Md Razeenuddin Mehdi Ответов: 2

Как оптимизировать этот цикл для O(n) или O(nlogn)

Ребята, я хочу выполнить этот цикл, надеюсь, в O(n). Мне просто нужно вычислить минимальное расстояние между вторым и первым вхождением всех элементов в массив.

например abcdeab ответ для m = 1

Что я уже пробовал:

m = INT_MAX
for(int i = 0; i<s.length(); ++i)
{
    for(int j = i+1; j<s.length(); ++j)
    {
        if(s[i] == s[j] and m > j - i)
        {
            m = j - i;
            if(m == 1)
                break;
        }
    }
}

2 Ответов

Рейтинг:
1

Patrice T

Цитата:
Как оптимизировать этот цикл для O(n) или O(nlogn)

Правило опытных программистов: во-первых, сделайте это правильно, а затем сделайте это быстро.
Цитата:
например abcdeab ответ для m = 1

Нет никакого способа, чтобы ответ был 1 !
К примеру есть 2 матча
First match is abcdeabb
               ^    ^
and second match is abcdeabb
                     ^    ^

Чтобы получить ответ = 1
the match is abcdeabb
                   ^^

а вот это второй и третий возникновение б.
Ваш алгоритм верен, если буква, появившаяся не более 2 раз, является строкой.

Вместо того чтобы проверять букву с остатком строки, Мой первый подход состоял бы в том, чтобы проверить букву С началом строки, чтобы убедиться, что буква проверяется с первым вхождением.

Я не думаю, что достижение вашей цели возможно.

Stefan_Lang

Согласовано по всем счетам, кроме последнего: вы можете сделать это в O(N) (на самом деле O(N+C), см. Решение 2)

Рейтинг:
0

Stefan_Lang

Вы можете сделать его O(N+C) , где C - количество допустимых символов в вашем алфавите. Попробовать это:

#include <iostream>
#include <limits>

int min_repetitions(char const* text) {

    int min_rep = -1; // indicates that no repetitions were found

    if (!text)
        return -1;

    std::ptrdiff_t positions[256] = {0 }; // o(number of valid characters)

    min_rep = std::numeric_limits<int>::max();
    bool repetition_found = false;
    
    for (char const* ptext = text; *ptext != 0; ++ptext) {
        char c = *ptext;
        if (positions[c]==0) {
            positions[c]=ptext-text;
        }
        else if (positions[c]>0) {
            int distance = ptext-text - positions[c];
            if (distance < min_rep) {
                min_rep = distance;
                repetition_found = true;
            }
            positions[c] = -1; // disable future checks
        }
    }
    
    if (!repetition_found)
        min_rep = -1;

    return min_rep;
}
int main()
{
    char test[] = "abcdeabb";
 
    int min_rep = min_repetitions(test);
    if (min_rep >= 0)
        std::cout << "Minimum repetition distance for " << test << " is: " << min_rep << std::endl;
    else
        std::cout << "The text "<< test << " has no repetitions" << std:.endl;

    return 0;
}