[已解决]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

def arr_split(array):

    length = len(array)

    index = 0

    max_num = 0

    block_num = 0

    while index < length:

        for i in range(index, length):

            if array[zxsq-anti-bbcode-i] > max_num:

                max_num = array[zxsq-anti-bbcode-i]

            if max_num <= index:

                block_num += 1

                index += 1

                break

            else:

                index += 1

    return block_num

跳转到最佳答案楼层

TJBEST

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

def fun374(arr):
    M = len(arr)
    result = 0
    hasBeenIn = 0
    while hasBeenIn < M:
        tempMax = arr[hasBeenIn]
        rest = tempMax + 1 - hasBeenIn
        for num in arr[hasBeenIn:]:
            if num <= tempMax:
                rest -= 1
            else:
                rest = rest + (num - tempMax) - 1
                tempMax = num
            if rest == 0:
                break
        result += 1
        hasBeenIn = tempMax + 1
    return result

TJBEST

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

def fun374(arr):
    def inner(num):
        return num*(num+1)//2
    result = 0
    index = 0
    total = 0
    for num in arr:
        total += num
        if total == inner(index):
            result += 1
        index += 1
    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

def f374(arr):
    cout = 1
    for i in range(1, len(arr)):
        m, n = max(arr[:i]), min(arr[i:])
        if m < n:
            cout = cout + 1
    return cout

def f374(arr):
    cout, num = 0, arr[0]
    for i, val in enumerate(arr):
        if val > num:
            num = val
        if num == i:
            cout = cout + 1           
    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

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

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

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

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

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

sunrise085

不带有分块的

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

带有分块的

def fun374(list1):
    list2=[]
    l=len(list1)-1
    result=1
    t=list1.index(0)
    m=0
    while t<l:
        if t!=0:
            if max(list1[:t])>t:
                return 0
        result+=1
        list2.append(list1[m:t+1])
        m=t+1
        t=list1.index(t+1)
    list2.append(list1[m:t+1])
    print(list2)
    return result
    
list1=[1,0,3,2,6,5,4,7,8,9]
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] ...

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

风魔孤行者

def f(arr):
    n = 0
    count = len(arr)
    brr = list(range(len(arr)))
    while n<len(arr):
        if brr[n] != arr[n]:
            for a in range(n+1,len(arr)):
                if sorted(arr[n:a+1]) == brr[n:a+1]:
                    count = count-(a-n)
                    n = a
                    break
        n += 1
    return count

ouyunfu

挑战一行代码：

def f374(arr):
    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 块

阴阳神万物主

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

def solve(arr:list,which:bool=False)->int:
    how = []
    l = len(arr)
    for i in range(1,l-1):
        if max(arr[(how[-1]-1 if how else 0):i])<min(arr[i+1:]):
            how.append(i+1)
    else:
        how.append(l)
    res = len(how)
    if which:
        how.insert(0,0)
        for i in range(1,res):
            print(arr[how[i-1]:how[i]],end=',')
        else:
            print(arr[how[-2]:])
    return res
if __name__ == '__main__':
    print('示例1 输出：',solve([4,3,2,1,0]))
    print('示例2 输出：',solve([1,0,2,3,4],1))