本文轉(zhuǎn)自微信公眾號(hào)："算法與編程之美"

1、問題描述

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) k，請(qǐng)你判斷是否可以把這個(gè)數(shù)組劃分成一些由 k 個(gè)連續(xù)數(shù)字組成的集合。

如果可以，請(qǐng)返回 True；否則，返回 False。

示例 1：

輸入：nums = [1,2,3,3,4,4,5,6], k = 4

輸出：true

解釋：數(shù)組可以分成 [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

解釋：數(shù)組可以分成 [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

解釋：數(shù)組不能分成幾個(gè)大小為 3 的子數(shù)組。

2、解決方案

剛剛拿到這道題，筆者想的是先找出數(shù)組中最小的一個(gè)數(shù)，然后根據(jù)k的值從數(shù)組中刪除相對(duì)應(yīng)的元素，比如k等于3，數(shù)組中最小數(shù)字為1，那么就從列表中刪除1，2，3三個(gè)元素，如果數(shù)組中沒有對(duì)應(yīng)的元素，那就該返回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
 
 

但是在第二個(gè)for循環(huán)里面有過多操作，如果k的值太大，那么代碼運(yùn)行內(nèi)存便會(huì)很大，在規(guī)定內(nèi)存內(nèi)運(yùn)行便會(huì)超時(shí)。于是筆者想到了第二種方法，雖然代碼量大一點(diǎn)，但是相對(duì)于第一種，時(shí)間復(fù)雜度更小，不容易超時(shí)，用集合找出數(shù)組中出現(xiàn)過的數(shù)字，再用字典統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)，設(shè)置判定條件，再根據(jù)連續(xù)判定條件返回對(duì)應(yīng)布爾型。

python代碼：

def isPossibleDivide(nums, k):
  n = len(nums)
  if n % k != 0:
return False
  # 用集合記錄可能的數(shù)字
  s = set(nums)
  minList = list(s)
  minList.sort()
  # 用字典存儲(chǔ)每個(gè)數(shù)字出現(xiàn)的次數(shù)
  d = dict()
  for num in nums:
if num not in d:
 d[num] = 0
d[num] += 1
  # 判斷每組是否可由k個(gè)連續(xù)數(shù)字構(gòu)成
  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、結(jié)語

在遇到這類編程題時(shí)，要運(yùn)用多種方法嘗試求解，考慮時(shí)間復(fù)雜度和空間復(fù)雜度等多方面因素尋找最優(yōu)解法。

到此這篇關(guān)于Python劃分?jǐn)?shù)組為連續(xù)數(shù)字集合的練習(xí)的文章就介紹到這了,更多相關(guān)Python劃分?jǐn)?shù)組為連續(xù)數(shù)字集合內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。