介紹

我們寫算法的目的是盡可能的采用時間復(fù)雜度和空間復(fù)雜度都很低的算法。所以優(yōu)化算法的時候我們都從時間和空間兩個維度去考核。時間復(fù)雜度的調(diào)優(yōu)可以使用遞歸，二分法，動態(tài)規(guī)劃等等。空間的復(fù)雜度調(diào)優(yōu)就要根據(jù)業(yè)務(wù)選擇合適的數(shù)據(jù)結(jié)構(gòu)，今天我們就看看如何選擇數(shù)據(jù)機構(gòu)？我們都聽過使用空間復(fù)雜度替換時間復(fù)雜度的方案。

案例

查找數(shù)組中出現(xiàn)次數(shù)最多的那個元素和出現(xiàn)的次數(shù)。
比如 intArrayOf(3, 7, 5, 7, 8, 2, 7, 3, 8)
方法1：

fun findMaxTimes(): Pair<Int, Int> {
    val a = intArrayOf(3, 7, 5, 7, 8, 2, 7, 3, 8)
    var maxTimes = 0
    var valueOfMaxTimes = 0
    for (i in a.indices) {
        var tmpTimes = 0
        var tmpValue = a[i]
        for (m in a.indices) {
            val tmpValue2 = a[m]
            if (tmpValue == tmpValue2) {
                tmpTimes++
            }
            if (tmpTimes > maxTimes) {
                maxTimes = tmpTimes
                valueOfMaxTimes = tmpValue
            }
        }
    }

    return Pair(valueOfMaxTimes, maxTimes)
}

這種方法可讀性高，邏輯就是使用兩層循環(huán)，每次使用外部循環(huán)的元素和數(shù)組內(nèi)的元素進行一一比較并且統(tǒng)計重復(fù)次數(shù)，找到最大重復(fù)次數(shù)的。這種算法的時間復(fù)雜度是O(n),空間復(fù)雜度沒變。
方法2

fun findMaxTimes2(): Pair<Int, Int> {
    val a = intArrayOf(3, 7, 5, 7, 8, 2, 7, 3, 8)

    val groupMap: MutableMap<Int, Int> = mutableMapOf()
    a.forEach {
        val tmp = groupMap[it] ?: 0
        groupMap[it] = tmp + 1
    }

    val entry = groupMap.maxWith(Comparator { o1, o2 -> (o1!!.value.compareTo(o2!!.value)) })

    return Pair(entry?.key?:0,entry?.value?:0)
}

方法2中使用一個map統(tǒng)計所有元素的出現(xiàn)次數(shù)，然后遍歷map找到最大次數(shù)的元素和次數(shù)。這種方法的時間復(fù)雜度是O(n),但是空間復(fù)雜度是O(n).
方法3

fun findMaxTimes3():Pair<Int,Int> {
    val a = intArrayOf(3, 7, 5, 7, 8, 2, 7, 3, 8)

    val b= IntArray(9)

    for (i in a) {
        val tmp = if(b[i]==0)1 else b[i]+1
        b[i]=tmp
    }

    var maxTimes=0
    var valueOfMaxTimes = 0
    for(p in b.withIndex()){
        if(maxTimes<p.value){
            maxTimes = p.value
            valueOfMaxTimes = p.index
        }
    }

    return valueOfMaxTimes to maxTimes
}

方法3有種取巧的方式了，因為數(shù)組的值都是10以內(nèi)，而且長度也是小于10，所以定義一個等長的數(shù)組b，其中b的下標對應(yīng)a數(shù)組的value，b的value存儲的是重復(fù)次數(shù)。這種方式在內(nèi)存方面會浪費一部分空間，比如極端情況下，a數(shù)組內(nèi)都是8，那么b數(shù)組的index是8的位置有值，其他位置的空間都是浪費掉了。同樣這種方法的時間和空間復(fù)雜度都是O(n)

總結(jié)

我們在算法優(yōu)化的時候，值得優(yōu)化的地方：
1.無效的計算和存儲，刪除無效的計算和存儲，節(jié)約時間和空間復(fù)雜度。
2.采用合適的數(shù)據(jù)結(jié)構(gòu)存儲可以實現(xiàn)時間復(fù)雜度向空間復(fù)雜度的轉(zhuǎn)移。
3.多層循環(huán)的時候，找到合適的跳轉(zhuǎn)條件，跳出循環(huán)。