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

目录
  • 1、问题描述
  • 2、解决方案
  • 3、结语

本文转自微信公众号："算法与编程之美"

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。

如下题解：

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

3、结语

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

到此这篇关于Python划分数组为连续数字集合的练习的文章就介绍到这了,更多相关Python划分数组为连续数字集合内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python基础学习之基本数据结构详解【数字、字符串、列表、元组、集合、字典】

    Python基础学习之基本数据结构详解【数字、字符串、列表、元组、集合、字典】

    本文实例讲述了Python基础学习之基本数据结构.分享给大家供大家参考,具体如下: 前言 相比于PHP,Python同样也是脚本解析语言,所以在使用Python的时候,变量和数据结构相对于编译语言来说都会简单许多,但是Python相比于PHP来说,变量类型的定义会比较严格:string->int的转换没有PHP那么方便.但这也让程序稳定性有所提升,例如和客户端交互的时候,数据库取出来的数字int和缓存取出来的数字(默认是string)需要手动进行转换(否则会有报错提示),而PHP不需要手动转换的

  • Python 数字转化成列表详情

    Python 数字转化成列表详情

    目录 1. digitize 2. Python判断对象是否可迭代 本篇阅读的代码实现了将输入的数字转化成一个列表,输入数字中的每一位按照从左到右的顺序成为列表中的一项. 本篇阅读的代码片段来自于30-seconds-of-python. 1. digitize def digitize(n): return list(map(int, str(n))) # EXAMPLES digitize(123) # [1, 2, 3] 该函数的主体逻辑是先将输入的数字转化成字符串,再使用map函数将字符

  • python ndarray数组对象特点及实例分享

    1.numpy数组是同质数组,即所有元素的数据类型必须相同. 2.ndarray数组一般要求所有元素的数据类型相同,下标从0开始,最后一个元素的下标为数组长度减1. 实例 import numpy as np a = np.arange(0, 5, 1) print(a) b = np.arange(0, 10, 2) print(b) 知识点扩充: 定义数组 >>> import numpy as np >>> m = np.array([[1,2,3], [2,3,

  • python计算数字或者数组的阶乘的实现

    今天写毕业设计的时候遇到了一个级数展开式,里面包含着一个求一个数组的阶乘运算,这里特来记录一下. # -*- coding:utf-8 -*- """ author: 15025 time: 2021/7/18 17:58 software: PyCharm Description: calculate factorial of a given number """ class PythonStudy: @staticmethod def fac

  • Python多进程共享numpy 数组的方法

    Python多进程共享numpy 数组的方法

    为什么要用numpy Python中提供了list容器,可以当作数组使用.但列表中的元素可以是任何对象,因此列表中保存的是对象的指针,这样一来,为了保存一个简单的列表[1,2,3].就需要三个指针和三个整数对象.对于数值运算来说,这种结构显然不够高效.     Python虽然也提供了array模块,但其只支持一维数组,不支持多维数组(在TensorFlow里面偏向于矩阵理解),也没有各种运算函数.因而不适合数值运算.     NumPy的出现弥补了这些不足. 引用:https://zhuanl

  • Python实战小项目之Mnist手写数字识别

    Python实战小项目之Mnist手写数字识别

    目录 程序流程分析图: 传播过程: 代码展示: 创建环境 准备数据集 下载数据集 下载测试集 绘制图像 搭建神经网络 训练模型 测试模型 保存训练模型 运行结果展示: 程序流程分析图: 传播过程: 代码展示: 创建环境 使用<pip install+包名>来下载torch,torchvision包 准备数据集 设置一次训练所选取的样本数Batch_Sized的值为512,训练此时Epochs的值为8 BATCH_SIZE = 512 EPOCHS = 8 device = torch.devi

  • Python神经网络TensorFlow基于CNN卷积识别手写数字

    Python神经网络TensorFlow基于CNN卷积识别手写数字

    目录 基础理论 一.训练CNN卷积神经网络 1.载入数据 2.改变数据维度 3.归一化 4.独热编码 5.搭建CNN卷积神经网络 5-1.第一层:第一个卷积层 5-2.第二层:第二个卷积层 5-3.扁平化 5-4.第三层:第一个全连接层 5-5.第四层:第二个全连接层(输出层) 6.编译 7.训练 8.保存模型 代码 二.识别自己的手写数字(图像) 1.载入数据 2.载入训练好的模型 3.载入自己写的数字图片并设置大小 4.转灰度图 5.转黑底白字.数据归一化 6.转四维数据 7.预测 8.显示

  • Python划分数组为连续数字集合的练习

    目录 1.问题描述 2.解决方案 3.结语 本文转自微信公众号:"算法与编程之美" 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

  • PHP重置数组为连续数字索引的几种方式总结

    比如这样的一个php数组: $arr = array( 1 => 'apple', 3 => 'banana', 5 => 'orange' ); 想要转换为这样的数组: $arr = array( 0 => 'apple', 1 => 'banana', 2 => 'orange' ); 1.推荐的方式 array_values 方法 这样方式无论对普通数组还是关联数组都适用 <?php $arr = array( 1 => 'apple', 3 =>

  • python判断列表的连续数字范围并分块的方法

    情况一:列表中的数字是连续数字(从小到大) from itertools import groupby lst = [1, 2, 3, 5, 6, 7, 8, 11, 12, 13, 19] # 连续数字 fun = lambda x: x[1]-x[0] for k, g in groupby(enumerate(lst), fun): l1 = [j for i, j in g] # 连续数字的列表 if len(l1) > 1: scop = str(min(l1)) + '-' + st

  • python把数组中的数字每行打印3个并保存在文档中的方法

    如下所示: arrs=[2,15,48,4,5,6,7,6,4,1,2,3,6,6,7,4,6,8] f=open('test.txt','w+') count=0 for temp in arrs: count+=1 print >> f,temp, if(count%3==0): print >> f f.close() 结果: 以上这篇python把数组中的数字每行打印3个并保存在文档中的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • python 计算数组中每个数字出现多少次--“Bucket”桶的思想

    python 计算数组中每个数字出现多少次--“Bucket”桶的思想

    题目: 解法一:比较元素是否相等 思路说明: 这种应该是普通人最先想到的解法,先获取到数组之后进行有小到大排序,然后初始化一个min=0(代表新数字的开始角标),然后遍历新数组的每一个元素,如果两个元素不相等,count等于i-min,然后再把i赋值给min,当i遍历到最后一个元素时,count等于数组长度-min(这里的min是上一轮循环后最后一组数字的第一个元素的角标),当然这种解法面试官不会喜欢? (m, n) = input().split() ar = [int(x) for x in

  • JavaScript实现找出数组中最长的连续数字序列

    原始题目: 给定一个无序的整数序列, 找最长的连续数字序列. 例如: 给定[100, 4, 200, 1, 3, 2], 最长的连续数字序列是[1, 2, 3, 4]. 小菜给出的解法: function maxSequence(array,step){ var _array = array.slice(), //clone array _step = 1, _arrayTemp = [], i = 0; var parseLogic = { //result container parseRe

  • Python语言描述最大连续子序列和

    求最大连续子序列的和是一个很经典很古老的面试题了,记得在刚毕业找工作面试那会也遇到过同款问题.今儿突然想起来,正好快到毕业季,又该是苦逼的应届生们各种面试的时候到了,就给写了一些小代码解决这个问题.也希望各位找工作的同志们都拿到心目中理想的offer,从此以后,战胜高富帅,赢取白富美,走上人生巅峰. 1.问题描述 假设有一数组(python里为list啦)[1,3,-3,4,-6,-1],求数组中最大连续子序列的和.例如在此数组中,最大连续子序列的和为5,即1+3+(-3)+4 = 5 2.O(

  • python基础入门之字典和集合

    python基础入门之字典和集合

    python 中有6大标准类型: 数字(Number) 字符串(String) 列表(List) 元组(Tumple) 集合(Set) 字典(Dictionary) 前面已经介绍了上面4种,还有下面两种来介绍一下. 正文 字典 字典看起来非常像json,是的非常非常像,但是我们起码需要明白的是json是一个字符格式,而字典是一种数据结构. 区别: 1)json的key只能是字符串,dict的key可以是任何可hash的对象,例如:字符串.数字.元组等. 2)json的key可以是有序.重复的:d

  • python中数组array和列表list的基本用法及区别解析

    目录 1. 定义 2. 两者不同点 3. 两者相同点 4. 基本用法 4.1 数组array的基本用法 4.2 列表list的基本用法 1. 定义 (1)数组array: 是同类型数据的有限集合(2)列表list: 是一系列按特定顺序排列的元素组成,可以将任何数据放入列表,且其中元素之间没有任何关系. 2. 两者不同点 (0)列表是直接可以在python中使用的:数组是python中numpy库的,所以需要import numpy后,才能使用:(1)列表中的元素数据类型可以不一样:数据中的元素数

  • 正则表达式实现匹配连续数字的方法

    实现的要求如下: 纯数字 5-7位之间 前三位相同 从第四位开始连续 如下面的例子: 11123 #正确 22234 #正确 33345 #正确 333456 #正确 2223456 #正确 0001234 #正确 00012345 #错误:此行长度超标 000234 #错误:第3位与第4位不连续 111235 #错误:第5位和第6位不连续 1.匹配三位相同数字 (\d)\1{2} 2.匹配连续数字 匹配连续数字可以通过零宽断言来匹配,当然也没什么好办法,只能通过列举,如下两行都可以匹配3位连续

随机推荐