时间戳

首页 > 解决方案 > 当有多个查询时，检查某些子数组是否已排序的有效方法是什么？

c++ - 当有多个查询时，检查某些子数组是否已排序的有效方法是什么？

问题描述

假设一个数组A = {5, 4, 3, 7, 9, 11, 2}。有K许多查询。在每个查询中，我将得到两个整数L和R位置0 <= L <= R < N（其中 N 是数组的大小）。我必须告诉A[L...R]子数组是否已排序。

例如，第一个查询要求我判断从索引 0 到 6（基于 0 的索引）的子数组是否已排序。答案是，A[0...6]没有排序。然后第二个查询要求我判断是否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;
    }
}

标签： c++algorithmsorting

解决方案

您可以单次遍历数据，在每个索引处存储列表减少的最接近的前一个索引。

然后查询将包括从范围的右侧索引进行查找，并将结果值与范围的左侧索引进行比较。

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 << "Sorted\n";
        else
            std::cout << "Not Sorted\n";
    }
}

没有嵌套循环，因此该解决方案具有线性运行时间。

推荐阅读