[牛客网-左老师]最短排序

迷南。 2022-08-10 06:13 180阅读 0赞

对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。

给定一个整数数组A及它的大小n，请返回最短子数组的长度。

测试样例：

[1,5,3,4,2,6,7],7

返回：4

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    /* 时间复杂度为O(n),空间复杂度为O(1) */
    class ShortSubsequence {
    public:
        int findShortest(vector<int> A, int n) {
            int i = 0;
            int mmax = 0,mmin = 0;
            int p1 = -1, p2 = -1;
    
            /* 从前往后遍历 */
            for(i = 0; i < n; i++)
            {
                if(0 == i)
                {
                    mmax = A[i];
                }
                else
                {
                    if(mmax <= A[i])
                    {
                        mmax = A[i];
                    }
                    else
                    {
                        p1 = i;
                    }
                }
            }
    
            /* 从后往前遍历 */
            for(i = n-1; i >= 0; i--)
            {
                if(n-1 == i)
                {
                    mmin = A[i];
                }
                else
                {
                    if(A[i] <= mmin)
                    {
                        mmin = A[i];
                    }
                    else
                    {
                        p2 = i;
                    }
                }
            }
    
            if(-1 == p1 && -1 == p2)
            {
                return 0;
            }
    
            return p1-p2+1;
        }
    };
    
    
    int main( void )
    {
        int a[7] = {1,1,3,4,5,6,7};
        MaxGap mg;
        vector<int> v(a,a+7);
    
        cout << mg.findMaxGap(v,7) << endl;
    
        return 0;
    }