数据结构和算法（二）-空间换取时间

介绍

我们写算法的目的是尽可能的采用时间复杂度和空间复杂度都很低的算法。所以优化算法的时候我们都从时间和空间两个维度去考核。时间复杂度的调优可以使用递归，二分法，动态规划等等。空间的复杂度调优就要根据业务选择合适的数据结构，今天我们就看看如何选择数据机构？我们都听过使用空间复杂度替换时间复杂度的方案。

案例

查找数组中出现次数最多的那个元素和出现的次数。
比如 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)
}

这种方法可读性高，逻辑就是使用两层循环，每次使用外部循环的元素和数组内的元素进行一一比较并且统计重复次数，找到最大重复次数的。这种算法的时间复杂度是O(n),空间复杂度没变。
方法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统计所有元素的出现次数，然后遍历map找到最大次数的元素和次数。这种方法的时间复杂度是O(n),但是空间复杂度是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有种取巧的方式了，因为数组的值都是10以内，而且长度也是小于10，所以定义一个等长的数组b，其中b的下标对应a数组的value，b的value存储的是重复次数。这种方式在内存方面会浪费一部分空间，比如极端情况下，a数组内都是8，那么b数组的index是8的位置有值，其他位置的空间都是浪费掉了。同样这种方法的时间和空间复杂度都是O(n)

总结

我们在算法优化的时候，值得优化的地方：
1.无效的计算和存储，删除无效的计算和存储，节约时间和空间复杂度。
2.采用合适的数据结构存储可以实现时间复杂度向空间复杂度的转移。
3.多层循环的时候，找到合适的跳转条件，跳出循环。

最后编辑于：2020.07.06 21:25:21