Python|劃分數組為連續數字的集合
- 2020 年 2 月 21 日
- 筆記
問題描述
給你一個整數數組 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循環 的時間複雜度，很容易導致此題超出很多網站的時間複雜度，但是可以當作為一種思路來看，我們的做題應該還是首先考慮時間複雜度的
實習主編 | 王楠嵐
責 編 | 李和龍
