配列を連続した数値の集合に分割するPythonの練習問題
この記事は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の過去の記事を検索するか、以下の記事を引き続きご覧ください。
関連
-
[解決済み】Pythonが見つからない。引数なしで実行するとMicrosoft Storeからインストールされる、または設定からこのショートカットを無効にする
-
[解決済み】WindowsでコマンドラインからJupyterを実行する
-
python-DataFrame-Error: ValueError: DataFrame のコンストラクタが正しく呼び出されていない!
-
[解決済み] Python3 で dict_keys の要素にインデックスでアクセスする
-
[解決済み] tf.layers.conv2d と tf.contrib.slim.conv2d の相違点
-
[解決済み] CygwinでのPip-3.2のインストール
-
[解決済み] 引数のアンパッキング:名前付き引数のみが*式の後に続くことができます。
-
[解決済み] シンプルオーディオで音楽再生を停止する方法
-
[解決済み] Pythonです。urllib.quoteをインポートする
-
[解決済み] 2つのファイルを比較し、共通する行を削除する
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み】Pipenv: コマンドは見つかりませんでした
-
[解決済み】NameError: name 'requests' is not defined [クローズド].
-
[解決済み] Pythonで高速Pingスイープ
-
[解決済み] JSON ValueError: プロパティ名:1行目2列目(char 1)が必要です。
-
[解決済み] Python用tkinterのインストール
-
[解決済み] PythonリクエストでSSLError(Read operation timed out)が発生しました。
-
python error TypeError:Cannot convert the series to class float
-
IndexError: Index 0 is out of bounds for axis 0 with size 0
-
XXX型のオブジェクトがJSONシリアライズ可能でない問題を解決する
-
pythonの未解決のリファレンスソリューション