1. ホーム
  2. スクリプト・コラム
  3. パイソン

配列を連続した数値の集合に分割するPythonの練習問題

2022-01-27 12:07:13

この記事はWeChat: "アルゴリズムとプログラミングの美学"から転載したものです。

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が3に等しいように、配列から対応する要素を削除するには、kの値に応じて、配列内の最小の数を見つけることだと思うし、配列内の最小の数は1であり、3要素のリストから1、2、3を削除すると、配列内の対応する要素がない場合は、それが偽を返す必要があります。

次の問題の解答です。

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
 
 



しかし、2番目の for のループでは、kの値が大きすぎると、コードが大量のメモリで実行され、指定されたメモリ内で実行するとタイムアウトしてしまいます。そこで、2番目の方法を思いつきました。これは、配列に現れる数字をコレクションで探し、それぞれの数字の出現回数を辞書で数え、判定条件を設定して、連続した判定条件に従って対応するブール値を返すというもので、少しコードが多くなりますが、最初の方法よりは複雑でなく、時間もかからない方法です。

Pythonのコードです。

def isPossibleDivide(nums, k):
     n = len(nums)
     if n % k ! = 0:
         return False
     # Record the possible numbers in a set
     s = set(nums)
     minList = list(s)
     minList.sort()
     # Store the number of occurrences of each number in a dictionary
     d = dict()
     for num in nums:
         if num not in d:
             d[num] = 0
         d[num] += 1
     # Determine if each group can be composed of k consecutive numbers
     m = n // k # m groups
     start = 0 # start position
     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で配列を連続した数の集合に分割する方法については、Script Houseの過去の記事を検索するか、以下の記事を引き続きご覧ください。