专栏首页算法与编程之美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]。

解决方案

这道题根据标准解答的答案来说其实是一道很简单的题,只需要通过贪心算法便可以解决。

这里我要介绍的是另外一种更加容易理解的方法:

首先我们先将我们的列表进行排序,便于接下来的判断

因为我们用到的方法是删除,所以我们在一开始先通过一个while循环,只要该列表长度大于0该程序就一直进行。 还有便是只要列表内数字信号与k个,直接跳出不符合。

然后我们一个一个遍历,从第一个数字开始,通过循环k-1次判断这个数后面的三个满足自己比前一个的大于一,如果满足,就符合,就将其装入我们另一个结果列表。

最后如果循环完也没有发现满足的数字,那么就直接“false”

Python代码:

def isPossibleDivide(nums,k): nums = sorted(nums) while len(nums) > 0: list1 = list(set(nums)) if len(list1) < k: return "False" else: wanted = list1[0:k] for n in range(k-1): if int(wanted[n]) != int(wanted[n+1])-1: return "False" else: n+=1 for i in wanted : nums.remove(i) return "Ture" print(isPossibleDivide([1,2,3,4],3))

结语

虽然这种方法看起来简便,但是因为for循环 的时间复杂度,很容易导致此题超出很多网站的时间复杂度,但是可以当作为一种思路来看,我们的做题应该还是首先考虑时间复杂度的

实习主编 | 王楠岚

责 编 | 李和龙

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:李和龙

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|“双指针法”解删除数组重复项问题

    Python算法题目中,掌握一定的方法和技巧或者说是了解基础解题规律,能够在解决更多复杂问题的过程中思路更清晰,算法更简单易懂。接下来用一个leetcode题目...

    算法与编程之美
  • Python|贪心算法解最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    算法与编程之美
  • Python|力扣周赛2

    你一个整数数组nums和一个正整数threshold,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。

    算法与编程之美
  • 【leetcode刷题】20T39-颜色分类

    https://leetcode-cn.com/problems/sort-color

    木又AI帮
  • 移动零

    一份执着✘
  • 基本算法-分而治之

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

    赵云龙龙
  • LintCode 奇偶分割数组题目分析代码

    desperate633
  • 漫画:常考的荷兰国旗问题你还不会吗?(初级)

    "荷兰国旗问题" 是计算机科学中的一个经典题目,它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

    程序员小浩
  • Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。...

    李海彬
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩

扫码关注云+社区

领取腾讯云代金券