Блог

Главная - Вопросы по программированию - Каков эффективный способ проверить, отсортированы ли некоторые подмассивы или нет при наличии нескольких запросов?

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

#c #algorithm #sorting

#c #алгоритм #сортировка

Вопрос:

Предположим, что массив A = {5, 4, 3, 7, 9, 11, 2} . Существует K количество запросов. В каждом запросе мне будут предоставлены два целых числа L и R где 0 <= L <= R < N (где N — размер массива). Я должен сказать, отсортирован ли A[L...R] подмассив.

Например, 1-й запрос просит меня сообщить, отсортирован ли подмассив с индексом от 0 до 6 (индекс на основе 0) или нет. Ответ таков: A[0...6] не отсортирован. Затем 2-й запрос просит меня сообщить, A[2...5] отсортирован или нет. Этот подмассив отсортирован. Вот как я к этому подошел. Есть ли какой-нибудь лучший подход?

 int main()
{
    int a[7] = { 5, 4, 3, 7, 9, 11, 2}, k = 2;

    for(int i = 1; i <= k; i  )
    {
        int l, r;
        cin >> l >> r;
        bool isSorted = true;
        for(int j = l; j < r; j  )
        {
            if(a[j] > a[j   1] )
            {
                isSorted = false;
                break;
            }
        }
        if(isSorted == true)
            cout << "Sorted" << endl;
        else
            cout << "Not Sorted" << endl;
    }
}

Комментарии:

1. Я искал ответы, но ничего не смог найти, вот почему я спросил здесь. Предположим, что массив {9, 1, 3, 5, 4, 2}. Теперь у меня есть 2 запроса. 1-й запрос Я должен сообщить, отсортирован ли подмассив с индексом от 1 до 6 (индекс на основе 1), а это не так. Затем во 2-м запросе я должен сообщить, отсортирован ли подмассив с индексом от 2 до 4 или нет, который отсортирован. Если я попробую наивный способ, в худшем случае это займет N * K времени (где N — размер массива, а K — количество запросов). Мой вопрос в том, есть ли какой-либо лучший подход?

2. Что, если вы просто кэшируете интервалы сразу после проверки: как отсортированные, так и сейчас. Все, что попадает в отсортированный интервал, сортируется. Пересекающиеся отсортированные интервалы могут быть объединены. Все, что содержит несортированный интервал в целом — несортировано. Несортированные интервалы «отключаются», как только вы изучаете больше.

3. Потому что размер массива не более 10 ^ 5, и также будет не более 10 ^ 5 запросов.

4. Вы могли бы упростить свой код, используя std::is_sorted()

5. Вы не прочитали, что я спросил. Также есть K запросов. Таким образом, это заняло бы O (n * K) раз.

Ответ №1:

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

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

 int main(void)
{
    constexpr int a[7] = { 5, 4, 3, 7, 9, 11, 2};
    constexpr size_t k = 2;
    constexpr size_t N = sizeof a/sizeof a[0];
    size_t b[N];

    { /* preprocess */
        size_t last_decrease = 0;
        b[0] = 0;
        for( int x = 1; x < N;   x )
        {
            if (a[x] < a[x-1]) last_decrease = x;
            b[x] = last_decrease;
        }
    }

    for(int i = 0; i < k; i  )
    {
        int l, r;
        std::cin >> l >> r;
        bool isSorted = l >= b[r];

        if (isSorted)
            std::cout << "Sortedn";
        else
            std::cout << "Not Sortedn";
    }
}

Нет вложенных циклов, поэтому это решение имеет линейное время выполнения.