本文转自微信公众号："算法与编程之美"
1、问题描述
给你一个整数数组 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]。
示例 2：
输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。
示例 3：
输入：nums = [3,3,2,2,1,1], k = 3
输出：true
示例 4：
输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。
2、解决方案
刚刚拿到这道题，笔者想的是先找出数组中最小的一个数，然后根据k的值从数组中删除相对应的元素，比如k等于3，数组中最小数字为1，那么就从列表中删除1，2，3三个元素，如果数组中没有对应的元素，那就该返回False。
如下题解：
|
1
2
3
4
5
6
7
8
9
10
11
|
def isPossibleDivide(nums, k):
nums = sorted(nums)
for _ in range(len(nums)//k):
minv = nums[0]
for _ in range(k):
if minv in nums:
nums.remove(a)
minv +=1
return len(nums) == 0
|
但是在第二个for循环里面有过多操作，如果k的值太大，那么代码运行内存便会很大，在规定内存内运行便会超时。于是笔者想到了第二种方法，虽然代码量大一点，但是相对于第一种，时间复杂度更小，不容易超时，用集合找出数组中出现过的数字，再用字典统计每个数字出现的次数，设置判定条件，再根据连续判定条件返回对应布尔型。
python代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
def isPossibleDivide(nums, k):
n = len(nums)
if n % k != 0:
return False
# 用集合记录可能的数字
s = set(nums)
minList = list(s)
minList.sort()
# 用字典存储每个数字出现的次数
d = dict()
for num in nums:
if num not in d:
d[num] = 0
d[num] += 1
# 判断每组是否可由k个连续数字构成
m = n // k # m组
start = 0 # 起始位置
for mi in range(m):
if start >= len(minList):
return False
minv = minList[start]
flag = True
t = start
for key in range(minv, minv + k):
if key not in d:
return False
if d[key] < 1:
return False
elif d[key] == 1:
d[key] -= 1
t += 1
elif d[key] > 1:
d[key] -= 1
if flag:
start = t
flag = False
if flag:
start = t
return True
|
3、结语
在遇到这类编程题时，要运用多种方法尝试求解，考虑时间复杂度和空间复杂度等多方面因素寻找最优解法。
到此这篇关于Python划分数组为连续数字集合的练习的文章就介绍到这了,更多相关Python划分数组为连续数字集合内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！