论坛 › Python交流 › Python：每日一题 375

zltzlt 发表于 2020-4-14 13:21:35

Python：每日一题 375

今天的题目：

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

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

示例：

输入：
输出：5
解释：你只需要对 进行升序排序，那么整个表都会变为升序排序。

{:10_298:}欢迎大家一起答题！{:10_298:}

kinkon 发表于 2020-4-14 13:35:34

本帖最后由 kinkon 于 2020-4-15 13:38 编辑

不知道理解对不对
def f375(arr):
    new = sorted(arr)
    if new == arr:
      return 0
    l, r = 0, len(arr) - 1
    while l <= r and new == arr or new == arr :
      if new == arr:
            l += 1
      if new == arr:
            r -= 1
    return r - l + 1

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

永恒的蓝色梦想 发表于 2020-4-14 13:46:23

占楼

TJBEST 发表于 2020-4-14 13:46:32

本帖最后由 TJBEST 于 2020-4-14 20:27 编辑

先来一个弱智的方法，可能比较慢。
def fun375(arr):
    M = len(arr)
    sorted_arr = sorted(arr)
    for left in range(0,M):
      if arr == sorted_arr:
            continue
      else:
            break
    else:
      return 0
    for right in range(M-1,left-1,-1):
      if arr == sorted_arr:
            continue
      else:
            break
    return right - left + 1

蒋博文 发表于 2020-4-14 14:17:58

占个楼

大川1234 发表于 2020-4-14 14:26:50

好难

March2615 发表于 2020-4-14 14:28:20

本帖最后由 March2615 于 2020-4-14 15:08 编辑

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

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


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

写的短一点的话
def daily375(arr: list) -> int:
    diff_index =
    if diff_index:
      return max(diff_index) - min(diff_index) + 1
    else:
      return 0

大周家的MSH 发表于 2020-4-14 14:47:48

list1 = eval(input())
list2 = sorted(list1)
p , q = 0 , len(list1)-1
a = 0
while True:
    if list1 == list2 or list1 ==list2:
      p = p + 1
      q = q - 1
    else:
      break
print('',format(q-p+1))
应该可以吧。。。

ouyunfu 发表于 2020-4-14 15:54:36

本帖最后由 ouyunfu 于 2020-4-14 16:07 编辑

def f375(arr):
    a=sorted(arr)
    b = !=a]
    return b[-1]-b+1

Fallenight 发表于 2020-4-14 16:16:32

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 发表于 2020-4-14 17:24:56

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

旅途Z 发表于 2020-4-14 22:58:13

本帖最后由 旅途Z 于 2020-4-15 23:33 编辑

总觉得写的有多余的部分，已修改，没有想到顺序情况返回值有问题
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:
            flag1 = 1
      if equal_array != 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 发表于 2020-4-15 00:47:19

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

776667 发表于 2020-4-15 09:12:08

本帖最后由 776667 于 2020-4-15 09:13 编辑

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

岚冰1234 发表于 2020-4-15 10:54:01

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

kinkon 发表于 2020-4-15 12:46:09

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

最后要按升序排序的，，就得把这5个元素拿出来排成升序再放回去变成，应该是这个意思了

zltzlt 发表于 2020-4-15 13:26:37

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




第一段代码的 nums 是……？

zltzlt 发表于 2020-4-15 13:29:32

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




第二段代码 50 ms

zltzlt 发表于 2020-4-15 13:30:07

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

43 ms

zltzlt 发表于 2020-4-15 13:30:40

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




63 ms

查看完整版本: Python：每日一题 375