Python|划分数组为连续数字的集合

问题描述

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。如果可以，请返回 True；否则，返回 False。

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4

输出：true

解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

解决方案

这道题根据标准解答的答案来说其实是一道很简单的题，只需要通过贪心算法便可以解决。

这里我要介绍的是另外一种更加容易理解的方法：

首先我们先将我们的列表进行排序，便于接下来的判断

因为我们用到的方法是删除，所以我们在一开始先通过一个while循环，只要该列表长度大于0该程序就一直进行。还有便是只要列表内数字信号与k个，直接跳出不符合。

然后我们一个一个遍历，从第一个数字开始，通过循环k-1次判断这个数后面的三个满足自己比前一个的大于一，如果满足，就符合，就将其装入我们另一个结果列表。

最后如果循环完也没有发现满足的数字，那么就直接“false”

Python代码：

def isPossibleDivide(nums,k): nums = sorted(nums) while len(nums) > 0: list1 = list(set(nums)) if len(list1) < k: return "False" else: wanted = list1[0:k] for n in range(k-1): if int(wanted[n]) != int(wanted[n+1])-1: return "False" else: n+=1 for i in wanted : nums.remove(i) return "Ture" print(isPossibleDivide([1,2,3,4],3))

结语

虽然这种方法看起来简便，但是因为for循环的时间复杂度，很容易导致此题超出很多网站的时间复杂度，但是可以当作为一种思路来看，我们的做题应该还是首先考虑时间复杂度的

实习主编 | 王楠岚

责编 | 李和龙