題目描述
Given an integer array, you need to find onecontinuous 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 theshortestsuch subarray and output its length.
Example:
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:
1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means
分析
本題是Leetcode一道簡(jiǎn)單難度的題目，考察數(shù)組的基本知識(shí)點(diǎn)。一般數(shù)組問題我們都可以想到先排序倚舀，排序之后會(huì)發(fā)現(xiàn)比較多的有趣的線索无埃。
本題要求找到能夠排序之后使全局?jǐn)?shù)組有序的子數(shù)組的長(zhǎng)度钝诚，要求解子數(shù)組的長(zhǎng)度隘截，我們需要知道子數(shù)組的起點(diǎn)和終點(diǎn)的下標(biāo)位置铲咨，那么問題就轉(zhuǎn)變?yōu)槿绾吻蠼庾訑?shù)組起點(diǎn)終點(diǎn)下標(biāo)問題固歪。
我們使用我們前面分析的策略蒜鸡，先對(duì)我們的數(shù)組排個(gè)序胯努，然后我們和原數(shù)組比較一下，看看有什么發(fā)現(xiàn)逢防。我們發(fā)現(xiàn)叶沛，通過一個(gè)元素一個(gè)元素的逐一比較，我們很容易就找到兩個(gè)數(shù)組中第一個(gè)不一樣元素的位置和最后一個(gè)不一樣元素的位置忘朝，這兩個(gè)位置正是我們要求解的子數(shù)組的起點(diǎn)和終點(diǎn)灰署，問題得到解決。
同時(shí)不要忘記對(duì)邊界條件的判斷辜伟，如果起點(diǎn)和終點(diǎn)都相等的時(shí)候氓侧，那么意味著子數(shù)組并不存在。
代碼
class Solution(object):
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
'''
[2, 6, 4, 8, 10, 9, 15]
[2, 4, 6, 8, 9, 10, 15]
start = 1
end = 5
'''
if not nums:
return 0
sortedNums = sorted(nums)
start = end = -1
length = 0
for i in range(len(nums)):
if nums[i] != sortedNums[i]:
if start == -1:
start = i
end = i
if start == end:
length = 0
else:
length = end - start + 1
return length
代碼截圖
視頻教程
中文講解
http://v.youku.com/v_show/id_XMzE0MDc0OTE4MA==.html?spm=a2hzp.8253869.0.0
https://www.youtube.com/watch?v=go1q1R3QLc0&feature=youtu.be
英文講解
http://v.youku.com/v_show/id_XMzE0MDgyMjY0NA==.html?spm=a2hzp.8253869.0.0
https://www.youtube.com/watch?v=s191hahgPPo&feature=youtu.be
推薦Channel
Youtube Channel
https://www.youtube.com/channel/UCgOBOym0p20QGvsccsWHc0A
Youtube Channel
Youku 頻道
http://i.youku.com/codingmonkey2017
Youku 頻道
