Python：每日一题 375

zltzlt

今天的题目：

给定一个整数数组，寻找连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

返回在找出的子数组中最短的子数组的长度。

示例：

输入：[2, 6, 4, 8, 10, 9, 15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

欢迎大家一起答题！

kinkon

不知道理解对不对

def f375(arr):
    new = sorted(arr)
    if new == arr:
        return 0
    l, r = 0, len(arr) - 1
    while l <= r and new[l] == arr[l] or new[r] == arr[r] :
        if new[l] == arr[l]:
            l += 1
        if new[r] == arr[r]:
            r -= 1
    return r - l + 1

再来一个O(n)的

def f375(arr):        
    n = len(arr)
    rp, lp = arr[0], arr[-1]
    l, r = n, 0
    for i in range(1, n):
        if arr[i] >= rp:
            rp = arr[i]
        else:
            r = i                
    for i in range(n - 2, -1, -1):
        if arr[i] <= lp:
            lp = arr[i]
        else:
            l = i
    return r - l + 1 if r > l else 0

永恒的蓝色梦想

占楼

TJBEST

先来一个弱智的方法，可能比较慢。

def fun375(arr):
    M = len(arr)
    sorted_arr = sorted(arr)
    for left in range(0,M):
        if arr[left] == sorted_arr[left]:
            continue
        else:
            break
    else:
        return 0
    for right in range(M-1,left-1,-1):
        if arr[right] == sorted_arr[right]:
            continue
        else:
            break
    return right - left + 1

蒋博文

占个楼

大川1234

好难

March2615

这两天不是做隔夜题感觉都简单了呢

    # 解题思路：
    # 比较原列表和排序后的列表，找出从左往右和从右往左最先不同的位置
    # 中间的即为最小子数组 -> 相减即可得到长度

def daily375(arr: list) -> int:
    sort_arr = sorted(arr)
    left, right = 0, len(arr)-1
    for i in range(len(arr)):
        if arr[i] == sort_arr[i]:
            left += 1
        else:
            break
    for j in range(len(arr)-1, -1, -1):
        if arr[j] == sort_arr[j]:
            right -= 1
        else:
            break
    if left >= right:
        return 0
    else:
        return right - left + 1

写的短一点的话

def daily375(arr: list) -> int:
    diff_index = [i for i, (a, b) in enumerate(zip(arr, sorted(arr))) if a != b]
    if diff_index:
        return max(diff_index) - min(diff_index) + 1
    else:
        return 0

大周家的MSH

list1 = eval(input())
list2 = sorted(list1)
p , q = 0 , len(list1)-1
a = 0
while True:
    if list1[p] == list2[p] or list1[q] ==list2[q]:
        p = p + 1
        q = q - 1
    else:
        break
print('',format(q-p+1))

应该可以吧。。。

ouyunfu

def f375(arr):
    a=sorted(arr)
    b = [i for i in range(len(arr)) if arr[i]!=a[i]]
    return b[-1]-b[0]+1

Fallenight

def new_sort(list):
        a = len(list)
        for each in list:
                if each == min(list):
                        a -= 1
                else:
                        break
        for each in reversed(list):
                if each == max(list):
                        a -=1
                else:
                        break
        print(a)

whosyourdaddy

def func375(arr):
    temp = sorted(arr)
    length = len(arr)
    maxs = 0
    mins = 0
    for i in range(length):
        if temp[i] != arr[i]:
            mins = i
            break
    for i in range(length-1,mins,-1):
        if temp[i] !=arr[i]:
            maxs = i
            break
    return maxs-mins+1

旅途Z

总觉得写的有多余的部分，已修改，没有想到顺序情况返回值有问题

import numpy as np


def partial_sort(array):
    equal_array = np.array(array).argsort()
    head = 0
    tail = len(equal_array)-1
    flag1 = 0
    flag2 = 0
    while head < tail:
        if equal_array[head] != head:
            flag1 = 1
        if equal_array[tail] != tail:
            flag2 = 1
        if flag1 and flag2:
            break
        elif not flag1:
            head += 1
        elif not flag2:
            tail -= 1
    if not flag1 and not flag2:
        return 0
    else:
        return tail-head+1

fan1993423

def fun375(a):
    b=sorted(a)
    if a==b:return 0
    for i in range(len(a)):
        if a[i]!=b[i]:
            l=i
            break
    for j in range(-1,-len(a),-1):
        if a[j]!=b[j]:
            r=len(a)+j+1
            break
    return r-l

776667

def fun375(x):
    sorted_x = sorted(x)
    if sorted_x == x:
        return 0
    for i in range(len(x)):
        if x[i] != sorted_x[i]:
            start = i
            break
    for i in range(len(x))[::-1]:
        if x[i] != sorted_x[i]:
            end = i
            break
    return end - start + 1

岚冰1234

只有我一个人没看懂什么意思吗，什么是连续的子数组，给的例子是输入：[2, 6, 4, 8, 10, 9, 15]
输出：5，这里面的值没有一个是连续的吧，所以他的子数组是啥，完全没搞懂题目的意思

kinkon

岚冰1234 发表于 2020-4-15 10:54
只有我一个人没看懂什么意思吗，什么是连续的子数组，给的例子是输入：[2, 6, 4, 8, 10, 9, 15]
输出：5， ...

最后要按升序排序的，[2, 6, 4, 8, 10, 9, 15]，就得把[6,4,8,10,9]这5个元素拿出来排成升序再放回去变成[2, 4, 6, 8, 9, 10, 15]，应该是这个意思了

zltzlt

kinkon 发表于 2020-4-14 13:35
不知道理解对不对

第一段代码的 nums 是……？

zltzlt

kinkon 发表于 2020-4-14 13:35
不知道理解对不对

第二段代码 50 ms

zltzlt

TJBEST 发表于 2020-4-14 13:46
先来一个弱智的方法，可能比较慢。

43 ms

zltzlt

March2615 发表于 2020-4-14 14:28
这两天不是做隔夜题感觉都简单了呢

63 ms