配列・標準ライブラリ

Kotlin 20 topics · 印刷対応 (A4)
各項目は 中身の変化(図)→ コード の順。配列操作と予選で使う標準ライブラリ。
生成 生成・初期化 1D / 2D / 値埋め

長さ N の 0 埋め・値埋め、2 次元配列、可変リスト。

IntArray(5)        → [0, 0, 0, 0, 0]
fill(-1)           → [-1,-1,-1,-1,-1]
2D h×w             → [[0,0,0], [0,0,0]]
val a = IntArray(n)                 // 0 埋め
val b = IntArray(n) { -1 }          // -1 埋め
val g = Array(h) { IntArray(w) }    // 2次元 h×w (0 埋め)
val list = mutableListOf<Int>()     // 可変リスト
走査 走査(添字つき) 値 / 添字 / 両方

値だけ / 添字だけ / 添字と値の両方を回す 3 パターン。

[10,20,30] → i=0:10  i=1:20  i=2:30
for (x in a) { }                    // 値
for (i in a.indices) { }            // 添字 (a[i])
for ((i, x) in a.withIndex()) { }   // 両方
編集 追加・取り出し(末尾/先頭) push/pop/shift/unshift

末尾の add/pop は O(1)。先頭の挿入/削除は配列だと O(N)、多用するなら Deque。

[1,2] +3(末尾) → [1,2,3]   pop → 3, 残 [1,2]
[1,2] 先頭0     → [0,1,2]   shift → 0, 残 [1,2]
val a = mutableListOf(1, 2)
a.add(3)                            // 末尾追加 (push)
val last = a.removeAt(a.size - 1)   // 末尾取り出し (pop)
a.add(0, 0)                         // 先頭挿入 (unshift, O(N))
val first = a.removeAt(0)           // 先頭取り出し (shift, O(N))
編集 連結・マージ concat / merge

2 つの列をつなぐ。両方ソート済みなら merge で O(N) に整列したまま結合。

[1,2] ++ [3,4] → [1,2,3,4]
ソート済 [1,3] と [2,4] を merge → [1,2,3,4]
val c = a + b                       // 連結 (新 List)
val merged = (a + b).sorted()       // つないで整列
編集 重複除去 distinct / unique

順序を保つ重複除去と、ソートして潰す方法。

[1,1,2,3,3] → [1,2,3]
val u = a.distinct()                // 順序保持
val us = a.toSortedSet().toList()   // ソート + 重複排除
探索 含む・位置 contains / indexOf

存在判定と添字。配列の contains は O(N)(多用なら Set 化で O(1))。

[5,3,9] 3を含む? → true   9の位置 → 2
val has = 3 in a                    // 含むか
val idx = a.indexOf(9)              // 無ければ -1
集計 合計・最大・最小 sum / max / min

合計はオーバーフローに注意(Long で受ける)。空配列の max/min は例外。

[3,1,2] → sum=6  max=3  min=1
val s = a.sumOf { it.toLong() }     // Long で集計 (溢れ防止)
val mx = a.max(); val mn = a.min()  // 空は例外 → maxOrNull()
集計 条件カウント・抽出 count / filter

条件を満たす個数を数える / 満たす要素だけ取り出す。

[1,2,3,4] → even を抽出 → [2,4]  cnt=2
val cnt = a.count { it % 2 == 0 }
val evens = a.filter { it % 2 == 0 }
変換 変換(map) 各要素を加工

各要素に同じ加工をして新しい列を作る。

[1,2,3] → ×2 → [2,4,6]
val b = a.map { it * 2 }            // List<Int>
整列 ソート(昇順・降順・キー) sort / desc / key

破壊的か非破壊か、降順、キー指定(複数キー)を押さえる。

[3,1,2] → 昇順 [1,2,3] / 降順 [3,2,1]
a.sort()                            // 破壊的・昇順
val asc = a.sorted()                // 非破壊 (List)
val desc = a.sortedDescending()
list.sortBy { it.second }           // キー指定
整列 反転・回転・スライス reverse / slice

反転、部分列の切り出し(半開区間 [l, r))、左 k 回転。

[1,2,3,4] → 反転 [4,3,2,1] / [1,3) = [2,3]
val r = a.reversed()                // List
val sub = a.slice(1..2)             // 添字 1..2
探索 最大の位置(argmax) 値でなく添字

「最大値そのもの」でなく「最大の添字」が欲しいとき。

[3,9,1] → maxIdx = 1 (値 9)
val idx = a.indices.maxByOrNull { a[it] }!!
集計 累積和 区間和を O(1)

前計算 O(N)、以後どの区間和も O(1)。pre は長さ N+1、半開区間で引く。

a=[1,2,3] → pre=[0,1,3,6]
sum[l,r) = pre[r] - pre[l]
val pre = LongArray(n + 1)
for (i in 0 until n) pre[i + 1] = pre[i] + a[i]
val s = pre[r] - pre[l]             // [l, r)
変換 2次元・転置 行列の行↔列

h×w を w×h に。grid[i][j] → t[j][i]。

[[1,2,3],
 [4,5,6]]  →  [[1,4],
              [2,5],
              [3,6]]
val t = Array(w) { j -> IntArray(h) { i -> g[i][j] } }
コレクション 優先度付きキュー 最小 / 最大ヒープ

Dijkstra・貪欲で頻出。「常に最小(or 最大)を取り出す」袋。

push 3,1,2 → poll → 1,2,3  (最小ヒープ)
add/poll は O(log N)
val pq = PriorityQueue<Int>()                 // 最小ヒープ
val mx = PriorityQueue<Int>(reverseOrder())   // 最大ヒープ
pq.add(3); pq.add(1)
val top = pq.poll()                           // 最小を取り出す
コレクション Deque / Queue / Stack 両端 push/pop

両端から出し入れできる。Queue は BFS、Stack は DFS に使う。

BFS=Queue(先入れ先出し) / DFS=Stack(後入れ先出し)
front [ . . . ] back
val dq = ArrayDeque<Int>()
dq.addLast(1); dq.addFirst(0)       // 両端追加
val f = dq.removeFirst(); val l = dq.removeLast()
// Queue=addLast/removeFirst, Stack=addLast/removeLast
コレクション Set(重複排除・存在判定) contains O(1)

重複を消す / 含まれるかを高速判定。順序つきが要るなら Tree/std::set。

[1,1,2,3] → {1,2,3}  (3 in set? → true)
val s = a.toHashSet()               // 重複排除
if (3 in s) { }                     // 存在判定 O(1)
val ts = a.toSortedSet()            // 順序つき (TreeSet)
コレクション Map(頻度カウント) 値 → 個数

出現回数の数え上げが定番。無いキーの既定 0 の扱いが言語差。

[a,b,a] → {a:2, b:1}
val cnt = HashMap<Int, Int>()
for (x in a) cnt[x] = (cnt[x] ?: 0) + 1
val c = cnt.getOrDefault(x, 0)
// a.groupingBy { it }.eachCount() でも
探索 二分探索(挿入位置) lower / upper bound

ソート済み配列で「x 以上が始まる位置」。x の個数 = upper - lower。

sorted=[1,3,5,7]  x=5
lower=2 (5以上の先頭) / upper=3 (5より大の先頭)
// list はソート済み
val i = a.toList().binarySearch(x)  // 見つかれば添字、無ければ -(挿入点)-1
val ins = if (i < 0) -i - 1 else i  // 挿入位置
文字列 文字列 ⇄ 配列 split / join

空白区切りで分解、配列を連結、文字単位の配列化。

"a b c" → split → [a, b, c]
[a, b, c] → join(" ") → "a b c"
val parts = s.split(" ")
val nums = s.split(" ").map { it.toInt() }
val joined = list.joinToString(" ")
val chars = s.toCharArray()