纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

刘仕豪   2021-11-18 我要评论
想了解Python划分数组为连续数字集合的练习的相关内容吗刘仕豪在本文为您仔细讲解Python划分数组为连续数字集合的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Python划分数组,连续数字,集合,划分数组下面大家一起来学习吧。

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

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那么就从列表中删除123三个元素如果数组中没有对应的元素那就该返回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、结语

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


相关文章

猜您喜欢

  • Docker制作镜像 Docker制作镜像的完整过程

    想了解Docker制作镜像的完整过程的相关内容吗水妖3在本文为您仔细讲解Docker制作镜像的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Docker制作镜像,Docker,镜像制作下面大家一起来学习吧。..
  • Java 插入排序 Java 十大排序算法之插入排序刨析

    想了解Java 十大排序算法之插入排序刨析的相关内容吗龍弟-idea在本文为您仔细讲解Java 插入排序的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Java,插入排序,Java,排序算法下面大家一起来学习吧。..

网友评论

Copyright 2020 www.tdogsoftware.com 【零度软件园】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式