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循環 的時間複雜度，很容易導緻此題超出很多網站的時間複雜度，但是可以當作為一種思路來看，我們的做題應該還是首先考慮時間複雜度的

實習主編 | 王楠岚

責 編 | 李和龍