您好,登录后才能下订单哦!
本篇内容介绍了“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]。
示例 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 的子数组。
刚刚拿到这道题,笔者想的是先找出数组中最小的一个数,然后根据k的值从数组中删除相对应的元素,比如k等于3,数组中最小数字为1,那么就从列表中删除1,2,3三个元素,如果数组中没有对应的元素,那就该返回False。
如下题解:
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代码:
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
“Python划分数组为连续数字集合的方法是什么”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。