0%

Kotlin - List

下一場 Kotlin Heroes 快要到了,所以決定寫一些 Kotlin 的東西,順便複習 Kotlin。(平常都沒在寫 Kotlin QQ)

List 就是類似 C++ 的 vector 的東西,不過會稍微有點不同。

可變與不可變

Kotlin 的 List、Set 和 Map 都分成 mutable 和 immutable 的版本,List 是不可修改的,而 MutableList 是可修改的,這是它和 C++ 的 vector 與 Java 的 List 的不同之處。

這樣的設計可以避免傳 reference 的時候亂改到 List 裡的東西,但在競程上不需要顧慮這個,所以我通常都直接用 MutableList。

可以這樣把 List l 轉成 MutableList:

1
l.toMutableList()

初始化

初始化的方式有兩種,第一種是用 mutableListOf

1
mutableListOf(1, 2, 3, ...)

第二種是用 constructor:

1
MutableList(10) { it }

小括號中的是大小,後面的大括號是 lambda expression,表示第 it 項的數值,所以這樣寫的話,得到的就是 {0,1,2,...,9}。如果要一開始都是 0,就在大括號裡寫 0 就好。

這兩種初始化方式都會在編譯期自動偵測型態,也可以強制規定型態:

1
2
mutableListOf<Any>(...)
MutableList<Any>(...) {...}

修改和讀取

修改和讀取的方式很簡單,用中括號就好了:

1
2
val a = mutableListOf(...)
println(a[0])

要遍歷陣列的話,可以用超潮的 lambda:

1
2
a.forEach { println(it) } // it 是某一項
a.forEachIndexed { i, it -> println("$i $it") } // i 是 index,it 是 a[i]

兩者的差別是 forEach 只會給每一項是什麼,而 forEachIndexed 會給這是第幾項和這項是什麼。

一些常用的:

  • a.size:大小
  • a.add(T):在後面加一項
  • a.clear():清空
  • removeAt(index):把某一項砍掉,注意複雜度是
  • a.isEmpty():是不是空的
  • a.isNotEmpty():是不是不是空的

排序

每一種 sort 都有兩個版本,sort 開頭的會直接改變原陣列,sorted 開頭的會回傳一個新的排序好的 List(注意是 List),按照用 C++ 打競程的習慣,我都會用改變原陣列的 sort。還有 Kotlin 的 sort 都基於 Java 的 Collections.sort(),所以它是 stable sort,複雜度是

最基本的排序就是 sort 和 sortDescending,分別是小排到大和大排到小,大小比對是依類別實作的 compareTo() 而定。

1
2
3
val a = mutableListOf(4, 8, 7, 6, 3)
a.sort()
println(a) // [3, 4, 6, 7, 8]

進階一點就是 sortBy 和 sortByDescending,可以指定要排序的依據,例如有一個數列 ,然後要將 按照 排序:

1
2
3
val a = readLine()!!.split(' ').map { it.toInt() }
val ans = MutableList(a.size) {it}
ans.sortBy { a[it] }

會根據 sortBy 後面的 lambda 的回傳值排序,it 是陣列裡的某一項,回傳值就是它要對應到的東西。

進階版是 sortWith,可以指定很多個判斷依據,就像 C++ 的 tuple 排序一樣,像是要先比較 ,再比較 ,再比較 ,就可以這樣寫:

1
ans.sortWith(compareBy({a[it]}, {b[it]}, {c[it]}))

要反過來排,就把 compareBy 改成 compareByDescending

要完全地自訂 comparator,可以這樣自己寫一個:

1
2
3
4
5
6
7
8
9
val comp = Comparator<Int>{ i, j ->
when {
a[i] != a[j] -> a[i] - a[j]
b[i] != b[j] -> b[i] - b[j]
c[i] != c[j] -> c[i] - c[j]
else -> 0
} // 回傳正數表示 i > j、負數表示 i < j、0 表示 i = j
}
ans.sortWith(comp)

二分搜

二分搜的 function 有兩種:binarySearchbinarySearchWith

binarySearch 最基本的用法,就是拿來找某個值出現在 List 中的哪裡。

1
2
val l = listOf(1, 2, 3);
println(l.binarySearch(2)) // 輸出 1

binarySearch(i) 表示要找到 List 中,i 出現在第幾項,因為是二分搜,所以 List 必須先按類型定義的 compareTo() 排序過,其他的用法都是在改變排序規則。進階用法是 binarySearch(i, comp)comp 是一個 comparator(就是要跟填在 sortWith 裡的那個一樣),表示 List 已經按照 comp 排序,求 i 出現在哪裡。

如果在 List 中找不到 i,如果 i 加入 List 後,仍滿足單調性的話它會在 t,那麼就會回傳 -t - 1,可以用 -(t + 1) 轉成正數。如果 i 應該被放在最後,那 t=l.size

至於如果有元素重複出現會如何,我們來看一下它的實作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public fun <T> List<T>.binarySearch(element: T, comparator: Comparator<in T>, fromIndex: Int = 0, toIndex: Int = size): Int {
rangeCheck(size, fromIndex, toIndex)

var low = fromIndex
var high = toIndex - 1

while (low <= high) {
val mid = (low + high).ushr(1) // safe from overflows
val midVal = get(mid)
val cmp = comparator.compare(midVal, element)

if (cmp < 0)
low = mid + 1
else if (cmp > 0)
high = mid - 1
else
return mid // key found
}
return -(low + 1) // key not found
}

可以看到只要遇到要找的元素,就會直接當成答案,所以在有重複出現的狀況下,不一定會得到哪一個答案,要依二分搜的過程而定。

但是通常我們會希望拿到的是「第一個或最後一個滿足 XX 條件」的位置,這個時候就要用進進階 (?) 版:

1
2
3
val l = listOf(1, 2, 3, 3, 4);
println(l.binarySearch { compareValues(3, it) })
// l 會被對應成 -1, -1, 0, 0, 1

填在 binarySearch 裡的 lambda 是用來把 List 裡的元素對成一個數字(所以那個 lambda 是 T -> int),這個對應到的數字的正負號要有單調性,必須是先負、零、再正,所以所有負數都要在零和正數之前、正數都要在負數和零後面。如果有多個 0,同樣不一定會回傳哪一個,所以我們要用一點別的方式來處理它。

如果找不到 0,同樣會回傳把 0 插入之後會在哪裡(用剛剛那樣計算出的負數表示),也就是第一個 1 的位置(或是 l.size,如果沒有 1 的話),這樣它就肯定唯一了。所以要求滿足某條件的第一個位置(注意這個條件要滿足不符合的元素都在符合的之前),可以這麼寫:

1
2
3
4
l.binarySearch {
if(condition(it)) 1
else -1
}

例如要找到第一個 的位置:

1
2
3
4
5
6
7
8
val l = listOf(1, 2, 3, 3, 4)
val condition = { it: Int ->
it >= 3
}
l.binarySearch {
if(condition(it)) 1
else -1
} // =-3

注意回傳的數字會是 -t - 1,要記得轉回 t

有了這個就可以寫出 C++ 裡的 lower_boundupper_bound 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 回傳第一個滿足 condition 的位置
fun <T> List<T>.binarySearchWith(condition: (T) -> Boolean): Int {
return binarySearch {
if(condition(it)) 1
else -1
}.let { -(it + 1) }
}

fun List<Int>.lowerBound(i: Int): Int {
return binarySearchWith { it >= i }
}

fun List<Int>.upperBound(i: Int): Int {
return binarySearchWith { it > i }
}

fun main(args: Array<String>) {
val l = listOf(1, 2, 3, 3, 4)
println(l.lowerBound(3)) // 2
println(l.upperBound(3)) // 4
}

最後是 binarySearchBy,寫法是:

1
l.binarySearchBy(123) { it + 87 }

它和 sortBy 很像,就是把元素用後面那個 lambda 對應成別的東西再二分搜,而 List 必須按 lambda 對應的東西排序過。