練習問題/解答例/配列から大きい要素とその添字を求めるプログラム/Python
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[問題文>練習問題#u170a96a]]
リストの要素数をn。上位の個数（今回は3）をkと呼ぶことにす...
----
解答例1。全要素ソートなので計算量 O(n log n)。kが小さいと...
arr = [12, 6, 8, 3, 10, 1, 0, 9]
a = list(range(len(arr)))
a.sort(key=arr.__getitem__, reverse=True)
print('\n'.join(f'{i} -> {arr[i]}' for i in a[:3]))
解答例2。初心者用。計算量 O(nk)。kが少し大きくなると不利。
a = [12, 6, 8, 3, 10, 1, 0, 9]
NEG_INF = min(a) - 1
for i in range(3):
mx = max(a)
i = a.index(mx)
print(f"{i} -> {mx}")
a[i] = NEG_INF
解答例3。ヒープを使う。計算量 O(n log k) で高速。kがnに近...
import heapq
arr = [12, 6, 8, 3, 10, 1, 0, 9]
top_k = heapq.nlargest(3, range(len(arr)), key=arr.__get...
print('\n'.join(f'{i} -> {arr[i]}' for i in top_k))
終了行:
[[問題文>練習問題#u170a96a]]
リストの要素数をn。上位の個数（今回は3）をkと呼ぶことにす...
----
解答例1。全要素ソートなので計算量 O(n log n)。kが小さいと...
arr = [12, 6, 8, 3, 10, 1, 0, 9]
a = list(range(len(arr)))
a.sort(key=arr.__getitem__, reverse=True)
print('\n'.join(f'{i} -> {arr[i]}' for i in a[:3]))
解答例2。初心者用。計算量 O(nk)。kが少し大きくなると不利。
a = [12, 6, 8, 3, 10, 1, 0, 9]
NEG_INF = min(a) - 1
for i in range(3):
mx = max(a)
i = a.index(mx)
print(f"{i} -> {mx}")
a[i] = NEG_INF
解答例3。ヒープを使う。計算量 O(n log k) で高速。kがnに近...
import heapq
arr = [12, 6, 8, 3, 10, 1, 0, 9]
top_k = heapq.nlargest(3, range(len(arr)), key=arr.__get...
print('\n'.join(f'{i} -> {arr[i]}' for i in top_k))
ページ名:
