本文轉自微信公眾號："算法與編程之美"
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。
如下題解：
|
1
2
3
4
5
6
7
8
9
10
11
|
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代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
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劃分數組為連續數字集合內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
