下一場 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，可以這樣自己寫一個：

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 有兩種：binarySearch 和 binarySearchWith。

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。

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

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 的話），這樣它就肯定唯一了。所以要求滿足某條件的第一個位置（注意這個條件要滿足不符合的元素都在符合的之前），可以這麼寫：

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

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

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_bound 和 upper_bound 了：

// 回傳第一個滿足 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 對應的東西排序過。

WiwiHo 的廢文專區

Kotlin - List

可變與不可變

初始化

修改和讀取

排序

二分搜