leetcode 581. 最短無秩序連続サブ配列【一次遍歴最適方法】
1190 ワード
方法1、先にsortしてから比較します.
実行時間:80 ms、Shortest Unsorted Continuous SubarayのC++コミットで34.15%のユーザーを破った
メモリ消費量:11.4 MB、Shortest Unsorted Continuous SubarayのC++コミットで69.79%のユーザーを破った
方法二、
1回の遍歴
【前半の現在の最大値よりも前から最後の値が小さいものを見つける】
【後半の現在の最小値より後から最後の値が大きいものを見つける】
実行時間:36 ms、Shortest Unsorted Continuous SubarayのC++コミットで97.79%のユーザーを破った
メモリ消費量:10.4 MB、Shortest Unsorted Continuous SubarayのC++コミットで91.37%のユーザーを破った
実行時間:80 ms、Shortest Unsorted Continuous SubarayのC++コミットで34.15%のユーザーを破った
メモリ消費量:11.4 MB、Shortest Unsorted Continuous SubarayのC++コミットで69.79%のユーザーを破った
class Solution {
public:
int findUnsortedSubarray(vector& nums) {
vector tmp(nums);
sort(tmp.begin(),tmp.end());
int a=nums.size(),b=0;
for(int i=0;i=0;j--)
{
if(nums[j]!=tmp[j])
{
b=j;break;
}
}
if(a>=b+1)
return 0;
return b-a+1;
}
};
方法二、
1回の遍歴
【前半の現在の最大値よりも前から最後の値が小さいものを見つける】
【後半の現在の最小値より後から最後の値が大きいものを見つける】
実行時間:36 ms、Shortest Unsorted Continuous SubarayのC++コミットで97.79%のユーザーを破った
メモリ消費量:10.4 MB、Shortest Unsorted Continuous SubarayのC++コミットで91.37%のユーザーを破った
class Solution {
public:
int findUnsortedSubarray(vector& nums) {
int n=nums.size(),a=nums[0],b=nums[n-1],l=-1,r=-2;
for(int i=1;i