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

简介: 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

 


结语

在遇到这类编程题时,要运用多种方法尝试求解,考虑时间复杂度和空间复杂度等多方面因素寻找最优解法。

目录
相关文章
|
23天前
|
数据处理 Python
彻底掌握Python集合:无序性、去重神器与高效集合运算指南
彻底掌握Python集合:无序性、去重神器与高效集合运算指南
|
16天前
|
BI 测试技术 索引
Python学习笔记之NumPy模块——超详细(安装、数组创建、正态分布、索引和切片、数组的复制、维度修改、拼接、分割...)-1
Python学习笔记之NumPy模块——超详细(安装、数组创建、正态分布、索引和切片、数组的复制、维度修改、拼接、分割...)
|
6天前
|
存储 数据挖掘 Python
使用Python集合高效统计Excel数据
使用Python集合高效统计Excel数据
20 7
|
12天前
|
Python
NumPy 是 Python 中的一个重要的科学计算包,其核心是一个强大的 N 维数组对象 Ndarray
【6月更文挑战第18天】NumPy的Ndarray是科学计算的核心,具有ndim(维度数)、shape(各维度大小)、size(元素总数)和dtype(数据类型)属性。方法包括T(转置)、ravel()(扁平化)、reshape()(改变形状)、astype()(转换数据类型)、sum()(求和)及mean()(计算平均值)。更多属性和方法如min/max等可在官方文档中探索。
34 5
|
12天前
|
Python
NumPy 是 Python 的一个强大的科学计算库,它允许你创建各种类型的数组
【6月更文挑战第18天】**NumPy**是Python的科学计算库,用于创建和操作多维数组。常用数组生成方法包括:`np.array()`从列表转换为数组;`np.zeros()`生成全零矩阵;`np.ones()`创建全一矩阵;`np.linspace()`产生等差序列;`np.arange()`创建等差数列;以及`np.eye()`生成对角线为1的二维数组。更多方法可查阅NumPy官方文档。
24 2
|
16天前
|
存储 索引 Python
【Python列表解锁】:掌握序列精髓,驾驭动态数据集合
【Python列表解锁】:掌握序列精髓,驾驭动态数据集合
|
16天前
|
存储 Python 容器
Python零基础入门-5 数据结构(集合和字典)
Python零基础入门-5 数据结构(集合和字典)
|
21天前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】
|
2天前
|
数据挖掘 Python
python数据分析常用图大集合
python数据分析常用图大集合
|
4天前
|
Python
python集合
python集合
5 0