[已解决]Python：每日一题 374

zltzlt

今天的题目：

数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）。

将这个数组分割成几个 “块”，并将这些块分别进行排序。

之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

求最多能将数组分成多少块。

示例 1：

输入：arr = [4, 3, 2, 1, 0]
输出：1
解释：将数组分成 2 块或者更多块，都无法得到所需的结果。例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序数组。

示例 2：

输入：arr = [1, 0, 2, 3, 4]
输出：4
解释：可以把它分成两块，例如 [1, 0], [2, 3, 4]。然而，分成 [1, 0], [2], [3], [4] 块数是最多的。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

旅途Z

2020-4-14 14:31:29

已修改 Orz

1. def arr_split(array):
   
2.     length = len(array)
   
3.     index = 0
   
4.     max_num = 0
   
5.     block_num = 0
   
6.     while index < length:
   
7.         for i in range(index, length):
   
8.             if array[i] > max_num:
   
9.                 max_num = array[i]
   
10.             if max_num <= index:
    
11.                 block_num += 1
    
12.                 index += 1
    
13.                 break
    
14.             else:
    
15.                 index += 1
    
16.     return block_num

复制代码

跳转到最佳答案楼层

TJBEST

先来个简单的，后面看看有没有好办法

1. def fun374(arr):
   
2.     M = len(arr)
   
3.     result = 0
   
4.     hasBeenIn = 0
   
5.     while hasBeenIn < M:
   
6.         tempMax = arr[hasBeenIn]
   
7.         rest = tempMax + 1 - hasBeenIn
   
8.         for num in arr[hasBeenIn:]:
   
9.             if num <= tempMax:
   
10.                 rest -= 1
    
11.             else:
    
12.                 rest = rest + (num - tempMax) - 1
    
13.                 tempMax = num
    
14.             if rest == 0:
    
15.                 break
    
16.         result += 1
    
17.         hasBeenIn = tempMax + 1
    
18.     return result

复制代码

TJBEST

第二个方法，用的求和公式。但是不知道速度如何？超时我想应该不会 O(n)的复杂度

1. def fun374(arr):
   
2.     def inner(num):
   
3.         return num*(num+1)//2
   
4.     result = 0
   
5.     index = 0
   
6.     total = 0
   
7.     for num in arr:
   
8.         total += num
   
9.         if total == inner(index):
   
10.             result += 1
    
11.         index += 1
    
12.     return result

复制代码

永恒的蓝色梦想

占楼

永恒的蓝色梦想

TJBEST 发表于 2020-4-13 14:08
@zltzlt 题有问题  [4, 3, 2, 1, 0] 分成【4】【3】【2】【1】【0】不可以吗？
我觉得此题改为最少可能更 ...

分成[4],[3],[2],[1],[0]之后，连起来是[4,3,2,1,0]，并没有按降序排列

冰河星云

为什么不能用其他语言答题啊

kinkon

1. def f374(arr):
   
2.     cout = 1
   
3.     for i in range(1, len(arr)):
   
4.         m, n = max(arr[:i]), min(arr[i:])
   
5.         if m < n:
   
6.             cout = cout + 1
   
7.     return cout

复制代码

1. def f374(arr):
   
2.     cout, num = 0, arr[0]
   
3.     for i, val in enumerate(arr):
   
4.         if val > num:
   
5.             num = val
   
6.         if num == i:
   
7.             cout = cout + 1           
   
8.     return cout

复制代码

TJBEST

永恒的蓝色梦想 发表于 2020-4-13 14:14
分成[4],[3],[2],[1],[0]之后，连起来是[4,3,2,1,0]，并没有按降序排列

好的，没看全题

永恒的蓝色梦想

冰河星云 发表于 2020-4-13 14:16
为什么不能用其他语言答题啊

你可以去力扣答

kinkon

例2感觉也有个问题，为什么要分成 [1, 0], [2, 3, 4]得4块，不分成[1], [0，2, 3, 4] 得5块

看错了，必须要升序啊
如果碰到【2,3,2,3,4】是不是算 0？

TJBEST

kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 [1, 0], [2, 3, 4]得4块，不分成[1], [0，2, 3, 4] 得5块

看错了，必 ...

数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）应该是不重复的

kinkon

TJBEST 发表于 2020-4-13 14:48
数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）应该是不重复的

对对，没认真审题啊，谢谢

March2615

写完啦 感觉是这几天最不费脑子的了

1. def daily374(arr: list) -> int:
   
2.     # 解题思路
   
3.     # 大小为i的数应该在arr[i]处
   
4.     # -> 遍历arr，如果index处max(arr[:index+1])是index则可以将前面分块
   
5.     # -> [1,0,2,3,4] -> [1,0|2|3|4]
   
6.     # -> [4,3,2,1,0,5] -> [4,3,2,1,0|5]
   
7.     max_value = ans = 0
   
8.     for index, value in enumerate(arr):
   
9.         max_value = max(max_value, value)
   
10.         if max_value == index:
    
11.             ans += 1
    
12.     return ans

复制代码

顺便思考了一下如果有重复的情况（稍微复杂了一点，但有了思路就很好写了）

1. # 如果arr可以重复呢
   
2. def daily374_1(arr: list) -> int:
   
3.     # 解题思路
   
4.     # arr[i] > arr[i+1]时需要排序 -> 遍历arr，记录下最大值
   
5.     # 如[1,2,1,3] -> [1,2,2,3] -> 分成[1|2,1|3]三块
   
6.     # 有个问题：[1,2,1,3,1,2,4] -> [1,2,2,3,3,3,4] -> [1|2,1|3,1,2|4] -> wrong
   
7.     # 解决方法：
   
8.     # 左边的最大值一定小于右边的最小值，找到符合的进行分段后继续对右边操作
   
9.     # [1,2,1,3,1,2,4] -> [1|2,1,3,1,2,4] -> [1|2,1,3,1,2|4]
   
10.     copy_arr = arr[:]
    
11.     ans = i =0
    
12.     while i < len(copy_arr)-1:
    
13.         i += 1
    
14.         left, right = max(copy_arr[:i]), min(copy_arr[i:])
    
15.         if left <= right:
    
16.             ans += 1
    
17.             copy_arr = copy_arr[i:]
    
18.             i = 0
    
19.     return ans + 1  # +1是最后一块

复制代码

不过感觉效率不会太高，while应该可以优化的

sunrise085

不带有分块的

1. def fun374(list1):
   
2.     l=len(list1)-1
   
3.     result=1
   
4.     t=list1.index(0)
   
5.     while t<l:
   
6.         if t!=0:
   
7.             if max(list1[:t])>t:
   
8.                 return 0
   
9.         result+=1
   
10.         t=list1.index(t+1)
    
11.     return result
    
12.    
    
13. list1=[1,0,3,2,6,5,4,7,8,9]
    
14. print(fun374(list1))

复制代码

带有分块的

1. def fun374(list1):
   
2.     list2=[]
   
3.     l=len(list1)-1
   
4.     result=1
   
5.     t=list1.index(0)
   
6.     m=0
   
7.     while t<l:
   
8.         if t!=0:
   
9.             if max(list1[:t])>t:
   
10.                 return 0
    
11.         result+=1
    
12.         list2.append(list1[m:t+1])
    
13.         m=t+1
    
14.         t=list1.index(t+1)
    
15.     list2.append(list1[m:t+1])
    
16.     print(list2)
    
17.     return result
    
18.    
    
19. list1=[1,0,3,2,6,5,4,7,8,9]
    
20. print(fun374(list1))

复制代码

March2615

kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 [1, 0], [2, 3, 4]得4块，不分成[1], [0，2, 3, 4] 得5块

看错了，必 ...

我认为是分成两块
[2,3,2,3,4] -> [2,3,2,3|4]
因为第一块[2,3,2,3]排序后是[2,2,3,3]，加上后面的[4]是符合题意的

kinkon

March2615 发表于 2020-4-13 15:43
我认为是分成两块
[2,3,2,3,4] -> [2,3,2,3|4]
因为第一块[2,3,2,3]排序后是[2,2,3,3]，加上后面的[4] ...

嗯嗯，总感觉理解题意比做题还难啊

风魔孤行者

1. def f(arr):
   
2.     n = 0
   
3.     count = len(arr)
   
4.     brr = list(range(len(arr)))
   
5.     while n<len(arr):
   
6.         if brr[n] != arr[n]:
   
7.             for a in range(n+1,len(arr)):
   
8.                 if sorted(arr[n:a+1]) == brr[n:a+1]:
   
9.                     count = count-(a-n)
   
10.                     n = a
    
11.                     break
    
12.         n += 1
    
13.     return count

复制代码

ouyunfu

挑战一行代码：

1. def f374(arr):
   
2.     return [sum(arr[:i])==i*(i-1)/2 for i in range(1,len(arr))].count(1)+1

复制代码

zltzlt

kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 [1, 0], [2, 3, 4]得4块，不分成[1], [0，2, 3, 4] 得5块

看错了，必 ...

不可能分成 0 块

阴阳神万物主

难度评级：简单
要素分析：比较
代码：

1. def solve(arr:list,which:bool=False)->int:
   
2.     how = []
   
3.     l = len(arr)
   
4.     for i in range(1,l-1):
   
5.         if max(arr[(how[-1]-1 if how else 0):i])<min(arr[i+1:]):
   
6.             how.append(i+1)
   
7.     else:
   
8.         how.append(l)
   
9.     res = len(how)
   
10.     if which:
    
11.         how.insert(0,0)
    
12.         for i in range(1,res):
    
13.             print(arr[how[i-1]:how[i]],end=',')
    
14.         else:
    
15.             print(arr[how[-2]:])
    
16.     return res
    
17. if __name__ == '__main__':
    
18.     print('示例1 输出：',solve([4,3,2,1,0]))
    
19.     print('示例2 输出：',solve([1,0,2,3,4],1))
    

复制代码