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,那麼就從列表中刪除1,2,3三個元素,如果數組中沒有對應的元素,那就該返回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、結語

在遇到這類編程題時,要運用多種方法嘗試求解,考慮時間復雜度和空間復雜度等多方面因素尋找最優解法。

到此這篇關於Python劃分數組為連續數字集合的練習的文章就介紹到這瞭,更多相關Python劃分數組為連續數字集合內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: