題目描述：

Given an integer array, you need to find one?continuous subarray?that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the?shortest?such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

?

Note:

Then length of the input array is in range [1, 10,000].

The input array may contain duplicates, so ascending order here means?<=

?

要完成的函數：

int findUnsortedSubarray(vector<int>& nums)?

?

說明：

1、這道題給了一個vector，要求找到一個子數組，當把這個子數組升序排列之后，整個數組也就升序排列了。要求找到那個最短的子數組。

2、我們可以先把數組升序排列，看一下數組中元素的最終位置，當某個元素未排序之前沒有在它的最終位置，那意味著這個元素必須被排列過，也就是會在子數組中。

題目給的例子，[2,6,4,8,10,9,15]，升序排列之后為[2,4,6,8,9,10,15]，我們可以看到4/6/9/10都沒有在最終位置上，這四個數必須被排列，元素8在最終位置上，但是由于整個子數組被升序排列，所以8也要包含在其中。

所以其實我們只需要找到——從左邊數起第一個沒有在最終位置的元素，和，從右邊數起第一個沒有在最終位置的元素。他們中間的元素必須被重新排列。

所以，代碼如下：

int findUnsortedSubarray(vector<int>& nums) {vector<int>nums1=nums;sort(nums.begin(),nums.end());int i,j;for(i=0;i<nums.size();i++){if(nums[i]!=nums1[i])break;}if(i==nums.size())//如果數組原先就是升序排列的return 0;for(j=nums.size()-1;j>=0;j--){if(nums[j]!=nums1[j])break;}return j-i+1;}

上述代碼實測55ms，beats 24.74% of cpp submissions。

?

3、改進：

這道題還有其他方法可以做，筆者最開始也是用的更加直接的方法……但是后來發現這個算法過程有點復雜……

等之后想到了再來更新吧。

?

轉載于:https://www.cnblogs.com/chenjx85/p/8992385.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的leetcode-581-Shortest Unsorted Continuous Subarray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。