c++ leetcode 배열 Shorted Unsorted Continuous Subarray

이 문제는 만약 [2,6,4,8,10,9,15,22,3]과 같은 벡터가 있다면

정렬이 되기 위해 고쳐야 할 원소의 갯수를 구하는 문제이다.

 

정렬이 된다면 [2,3,4,6,8,9,10,15,22]일 것이다.

따라서 고쳐야 할 배열의 원소들은 [6,4,8,10,9,15,22,3]이고

그렇다면 이 원소의 갯수는 8이다.

 

O(nLogN)의 복잡도로 푸는 것은 쉽다.

오른쪽 배열은 퀵 소트로 정렬하였다.

[2,6,4,8,10,9,15,22,3] = [2,3,4,6,8,9,10,15,22]

다른 부분의 처음과 끝의 인덱스만 구하면 되기 때문이다.

 

하지만 O(N)으로 푸는 것은 꽤나 까다롭다.

O(nLogn) case와 O(N)의 케이스를 적어 놓겠다.

 

코드 >>

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
// Shorted Unsorted Continuous Subarray
// nums [2,6,4,8,10,9,15,22,3]
// output [6,4,8,10,9,15,22,3] (8개)
 
// O(nLogn)
int findUnsortedSubarray2(std::vector<int>& nums)
{
    std::vector<int> sorted_nums = nums;
    std::sort(sorted_nums.begin(), sorted_nums.end());
    std::vector<int> indexes;
    int min = 999;
    int max = -999;
    for (int i = 0; i < (int)sorted_nums.size(); i++)
    {
        if (nums[i] != sorted_nums[i])
        {
            indexes.emplace_back(i);
        }
    }
 
    if (indexes.size() == 0)
    {
        return 0;
    }
    else
    {
        return indexes[indexes.size() - 1] - indexes[0] + 1;
    }
 
}
 
 
// O(N)
int findUnsortedSubarray(std::vector<int>& nums)
{
    int min = 9999;
    int max = -9999;
    int vec_size = (int)nums.size();
    int l = 0;
    int r = vec_size-1;
    //bool flag = false;
 
    for (int i = 1; i < vec_size-2; i++)
    {
        if ((nums[i] < min) && (nums[i-1]>=nums[i]) && (nums[i+1]>=nums[i]))
        {
            min = std::min(nums[i], min);
        }
    }
    for (int i = vec_size - 2; i >= 1; i--)
    {
        if ((nums[i] > max)&&(nums[i+1]<=nums[i])&&(nums[i-1]<=nums[i]))
        {
            max = std::max(nums[i], max);
        }
    }
 
    
    
    if (min == INT64_MAX)
    {
        l = 0;
    }
    if (max == INT64_MIN)
    {
        r = vec_size-1;
    }
 
    for (int i = 0; i < vec_size; i++)
    {
        if (nums[i] > min)
        {
            l = i;
            break;
        }
    }
 
    for (int j = vec_size-1; j >= 0; j--)
    {
        
        if (nums[j] < max)
        {
            r = j;
            break;
        }
    }
    std::cout << "r : " << r << " l : " << l << std::endl;
    std::cout << "max : " << max << " min : " << min << std::endl;
    return (r - l) != (vec_size-1) ? (r - l+1) : 0;
}
 
 
int main()
{
    std::vector<int> nums = { 2, 6, 4, 8, 10, 9, 15,22,3 };
    //std::vector<int> nums = { 1,2,3,4 };
    // O(n)
    int ans = findUnsortedSubarray(nums);
    //O(nLogN)
    //int ans = findUnsortedSubarray2(nums);
    std::cout << ans << std::endl;
 
    return 0;
}