Python：每日一题 375

zltzlt

今天的题目：

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

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

示例：

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

欢迎大家一起答题！

kinkon

不知道理解对不对

1. def f375(arr):
   
2.     new = sorted(arr)
   
3.     if new == arr:
   
4.         return 0
   
5.     l, r = 0, len(arr) - 1
   
6.     while l <= r and new[l] == arr[l] or new[r] == arr[r] :
   
7.         if new[l] == arr[l]:
   
8.             l += 1
   
9.         if new[r] == arr[r]:
   
10.             r -= 1
    
11.     return r - l + 1

复制代码

再来一个O(n)的

1. def f375(arr):        
   
2.     n = len(arr)
   
3.     rp, lp = arr[0], arr[-1]
   
4.     l, r = n, 0
   
5.     for i in range(1, n):
   
6.         if arr[i] >= rp:
   
7.             rp = arr[i]
   
8.         else:
   
9.             r = i               
   
10.     for i in range(n - 2, -1, -1):
    
11.         if arr[i] <= lp:
    
12.             lp = arr[i]
    
13.         else:
    
14.             l = i
    
15.     return r - l + 1 if r > l else 0

复制代码

永恒的蓝色梦想

占楼

TJBEST

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

1. def fun375(arr):
   
2.     M = len(arr)
   
3.     sorted_arr = sorted(arr)
   
4.     for left in range(0,M):
   
5.         if arr[left] == sorted_arr[left]:
   
6.             continue
   
7.         else:
   
8.             break
   
9.     else:
   
10.         return 0
    
11.     for right in range(M-1,left-1,-1):
    
12.         if arr[right] == sorted_arr[right]:
    
13.             continue
    
14.         else:
    
15.             break
    
16.     return right - left + 1

复制代码

蒋博文

占个楼

大川1234

好难

March2615

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

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

复制代码

1. def daily375(arr: list) -> int:
   
2.     sort_arr = sorted(arr)
   
3.     left, right = 0, len(arr)-1
   
4.     for i in range(len(arr)):
   
5.         if arr[i] == sort_arr[i]:
   
6.             left += 1
   
7.         else:
   
8.             break
   
9.     for j in range(len(arr)-1, -1, -1):
   
10.         if arr[j] == sort_arr[j]:
    
11.             right -= 1
    
12.         else:
    
13.             break
    
14.     if left >= right:
    
15.         return 0
    
16.     else:
    
17.         return right - left + 1

复制代码

写的短一点的话

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

复制代码

大周家的MSH

1. list1 = eval(input())
   
2. list2 = sorted(list1)
   
3. p , q = 0 , len(list1)-1
   
4. a = 0
   
5. while True:
   
6.     if list1[p] == list2[p] or list1[q] ==list2[q]:
   
7.         p = p + 1
   
8.         q = q - 1
   
9.     else:
   
10.         break
    
11. print('',format(q-p+1))

复制代码

应该可以吧。。。

ouyunfu

1. def f375(arr):
   
2.     a=sorted(arr)
   
3.     b = [i for i in range(len(arr)) if arr[i]!=a[i]]
   
4.     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

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

1. import numpy as np
   
2. 
   
3. 
   
4. def partial_sort(array):
   
5.     equal_array = np.array(array).argsort()
   
6.     head = 0
   
7.     tail = len(equal_array)-1
   
8.     flag1 = 0
   
9.     flag2 = 0
   
10.     while head < tail:
    
11.         if equal_array[head] != head:
    
12.             flag1 = 1
    
13.         if equal_array[tail] != tail:
    
14.             flag2 = 1
    
15.         if flag1 and flag2:
    
16.             break
    
17.         elif not flag1:
    
18.             head += 1
    
19.         elif not flag2:
    
20.             tail -= 1
    
21.     if not flag1 and not flag2:
    
22.         return 0
    
23.     else:
    
24.         return tail-head+1

复制代码

fan1993423

1. def fun375(a):
   
2.     b=sorted(a)
   
3.     if a==b:return 0
   
4.     for i in range(len(a)):
   
5.         if a[i]!=b[i]:
   
6.             l=i
   
7.             break
   
8.     for j in range(-1,-len(a),-1):
   
9.         if a[j]!=b[j]:
   
10.             r=len(a)+j+1
    
11.             break
    
12.     return r-l

复制代码

776667

1. def fun375(x):
   
2.     sorted_x = sorted(x)
   
3.     if sorted_x == x:
   
4.         return 0
   
5.     for i in range(len(x)):
   
6.         if x[i] != sorted_x[i]:
   
7.             start = i
   
8.             break
   
9.     for i in range(len(x))[::-1]:
   
10.         if x[i] != sorted_x[i]:
    
11.             end = i
    
12.             break
    
13.     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