演算法十八般武藝

• 演算法十八般武藝
  • 278. First Bad Version
    • 嘗試一：線性搜尋 (Linear Search)
    • 嘗試二：指數搜尋 (Exponential search) / 深度優先搜尋(Depth-First-Search, a.k.a DFS)
    • 嘗試三：二分搜尋法 (Binary Search)
    • 嘗試四：插值搜尋 (Interpolation Search)
  • 912. Sort an Array
    • 嘗試一：猴子排序(Bogo Sort)
    • 嘗試二：臭皮匠排序 (Stooge Sort)
    • 嘗試三：慢速排序 (Slow Sort)
    • 嘗試四：泡沫排序 (Bubble Sort)
    • 嘗試五：快速排序 (Quick Sort)
    • 嘗試六：選擇排序 (Selection Sort)
    • 嘗試七：合併排序 (Merge Sort)
    • 嘗試八：堆積排序 (Heap Sort)
    • 嘗試九：計數排序 (Counting Sort)
    • 嘗試十：鴿巢排序 (Pigeonhole Sort)
    • 嘗試十一：閃電排序 (Flash Sort)
    • 嘗試十二：基數排序 (Radix Sort)

278. First Bad Version

簡介：給定一數 n 作為版本，該數內存在一值為壞掉的版本，而該值後的數字皆為壞掉的版本，求該值。

嘗試一：線性搜尋 (Linear Search)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $O(1)$
• 最壞時間複雜度：
  $O(n)$
• 平均時間複雜度：
  $O(\frac{n}{2})$

概念

根據題目，我們可以用單純從

$0$到

$n$逐一判斷是否是壞掉的版本，而第一個遇到的壞掉的版本即是答案：

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        for (i in 0 .. n) {
            if (isBadVersion(i)) {
                return i
            }
        }
        return n
	}
}

執行結果

TLE原因

根據該演算法推算，若給定一邊緣測資：

n = 2^31 - 1
bad = 2^31 - 1 = n

則該測資的時間複雜度為

$O(2^{31-1})$，每次迭代若花費

$0.1$ms，則需花費

$59.7$小時執行。

不論是由頭或是尾端開始線性搜尋，若測資過於極端，將會導致TLE。

嘗試二：指數搜尋 (Exponential search) / 深度優先搜尋(Depth-First-Search, a.k.a DFS)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $O(1)$
• 最壞時間複雜度：
  $O(\log (i))$
• 平均時間複雜度：
  $O(\log (i))$

以指數搜尋為例

概念

指數搜尋利用指數的成長性來逐步擴大搜尋範圍，並直到指數超過/到達所搜尋的值，後利用其他搜尋演算法於該值域進行二次搜尋。

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

import kotlin.math.min

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var exp = 1
        
        while (exp < n && !isBadVersion(exp))
            exp *= 2
        
        return binarySearch(n, exp / 2, min(exp + 1, n))
	}
    
    fun binarySearch(n: Int, low: Int, high: Int): Int {
        var lo = low
        var hi = high
        var mid = 0
        
        while (lo < hi) {
            mid = lo + (hi - lo) / 2
            
            if (isBadVersion(mid)) {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        
        return hi
    }
}

執行結果

TLE原因

由於DFS用在數列上的效果和指數搜尋是相同的，所以我們放在一起討論。
根據指數底數的不同，對於增長的速度也會有所不同，若根據題目的邊緣測資：

n = 2^31 - 1
bad = 2^31 - 1 = n

當我們使用

$2$作為底數，

$2$要迭代

$32$次才能得到範圍進行下一步的搜尋；
當我們使用

$10$作為底數，

$10$只要迭代

$9$次就能得到範圍進行下一步的搜尋，但對於後續的搜尋因為範圍過大，反而會導致搜尋效率低落。

嘗試三：二分搜尋法 (Binary Search)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $1$
• 最壞時間複雜度：
  $\log (n)$
• 平均時間複雜度：
  $\log (n)$

概念

根據題目，我們可以藉由判斷是否是壞掉的版本來縮小搜尋範圍，若是壞掉的版本，則第一個壞掉的版本不是這個壞掉的版本就是在這個之前。

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var lo = 0
        var hi = n
        var mid = 0
        
        while (lo < hi) {
            mid = lo + (hi - lo) / 2
            
            if (isBadVersion(mid)) {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        
        return hi
	}
}

執行結果

嘗試四：插值搜尋 (Interpolation Search)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $1$
• 最壞時間複雜度：
  $n$
• 平均時間複雜度：
  $\log (\log (n))$

概念

同二分搜尋，差異在於使用插值公式來計算猜測搜尋鍵值的位置。

$pos=low+\frac{(high-low)\cdot (key-ar{r}_{low})}{ar{r}_{high}-ar{r}_{low}}$

實作

基於其公式的要求，該公式要求給定要搜尋的值 key ，故本題不適用。

912. Sort an Array

嘗試一：猴子排序(Bogo Sort)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $O(n)$
• 最壞時間複雜度：
  $O(\mathrm{\infty })$
• 平均時間複雜度：
  $O(n\cdot n!)$

概念

猴子排序的概念同 無限猴子定律，即每次檢查若未整齊排序，則全部打散再重複執行，直到整齊排序。

猴子排序在極小的陣列中效果和一般的排序是幾乎沒有差異的，但隨著陣列越大，其不可靠性也就越大。

class Solution {
    fun isSorted(nums: List<Int>): Boolean {
        for (i in 0 until nums.size - 1)
            if (nums[i] > nums[i + 1])
                return false
        return true
    }
    
    fun sortArray(nums: IntArray): IntArray {
        val tmpNums = nums.toList()
        while (!isSorted(tmpNums))
            tmpNums.shuffled()
        return tmpNums.toIntArray()
    }
}

執行結果

TLE原因

由於其極高的不穩定性，導致每次迭代對於次迭代是無影響的，也就是說，每次的時間花費對於整齊排序這個目標是沒有實質幫助的。

嘗試二：臭皮匠排序 (Stooge Sort)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $?$
• 最壞時間複雜度：
  $O(n^{\frac{\log (3)}{\log (1.5)}})$
• 平均時間複雜度：
  $?$

概念

根據Wikipedia的實現：

• 如果最後一個值小於第一個值，則交換這兩個數
• 如果當前集合元素數量大於等於
  $3$：
• 1. 使用臭皮匠排序法排序前
     $\frac{2}{3}$的元素
• 2. 使用臭皮匠排序法排序後
     $\frac{2}{3}$的元素
• 3. 再次使用臭皮匠排序法排序前
     $\frac{2}{3}$的元素

import kotlin.math.round

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return stoogeSort(nums)
    }
    
    fun stoogeSort(nums: IntArray, i1: Int = 0, i2: Int = nums.size - 1): IntArray {
        if (nums[i1] > nums[i2]) {
            val tmp = nums[i1]
            nums[i1] = nums[i2]
            nums[i2] = tmp
        }
        
        if (i2 - i1 + 1 >= 3) {
            val t = round((i2 - i1 + 1) / 3.0).toInt()
            
            stoogeSort(nums, i1, i2 - t)
            stoogeSort(nums, i1 + t, i2)
            stoogeSort(nums, i1, i2 - t)
        }
        
        return nums
    }
}

執行結果

TLE原因

根據演算法的最壞時間複雜度，代入該題的最大上限值

$5\cdot {10}^4$，可以發現最大的迭代次數約為

$991$次，不考慮比較數字所花費的時間，顯然使用該演算法仍不符合效益。

嘗試三：慢速排序 (Slow Sort)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $?$
• 最壞時間複雜度：
  $?$
• 平均時間複雜度：
  $O(n^{\log (n)})$ or
  $\mathrm{\Omega }(n^{\frac{{\log }_2(n)}{(2+ϵ)}})$ for any
  $ϵ>0$

概念

根據Wikipedia，慢速排序基於合併排序的分而治之及遞迴的思想，並故意設計使排序過程非常緩慢。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return slowSort(nums)
    }
    
    fun slowSort(nums: IntArray, i1: Int = 0, i2: Int = nums.size - 1): IntArray {
        if (i1 >= i2) return nums
        val m = (i1 + i2) / 2
        
        slowSort(nums, i1, m)
        slowSort(nums, m + 1, i2)
        
        if (nums[i2] < nums[m])
        {
            val tmp = nums[i2]
            nums[i2] = nums[m]
            nums[m] = tmp
        }

        slowSort(nums, i1, i2 - 1)
        
        return nums
    }
}

執行結果

TLE原因

根據演算法的最壞時間複雜度，代入該題的最大上限值

$5\cdot {10}^4$，可以發現最大的迭代次數約為1.2031481e+22次，不考慮比較數字所花費的時間，顯然使用該演算法仍不符合效益。

嘗試四：泡沫排序 (Bubble Sort)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $O(n)$
• 最壞時間複雜度：
  $O(n^2)$
• 平均時間複雜度：
  $O(n^2)$

概念

藉由重複走訪過要排序的數列，一次比較兩個元素並交換，直到整齊排序。該演算法得名於其操作過程中元素逐漸浮 到數列的頂端。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return bubbleSort(nums)
    }
    
    fun bubbleSort(nums: IntArray): IntArray {
        for (i in nums.indices) {
            for (j in 0 .. nums.size - 2 - i) {
                if (nums[j] > nums[j + 1]) {
                    val tmp = nums[j]
                    nums[j] = nums[j + 1]
                    nums[j + 1] = tmp
                }
            }
        }
        
        return nums
    }
}

執行結果

TLE原因

根據演算法的最壞時間複雜度，代入該題的最大上限值

$5\cdot {10}^4$，可以發現最大的迭代次數約為

$2500000000$次，不考慮比較數字所花費的時間，顯然使用該演算法仍不符合效益。

嘗試五：快速排序 (Quick Sort)

簡介

• 實作難易度：中等 至 困難
• 最佳時間複雜度：
  $O(n\cdot \log (n))$
• 最壞時間複雜度：
  $O(n^2)$
• 平均時間複雜度：
  $O(n\cdot \log (n))$

概念

根據Wikipedia，快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的

$2$個子序列，然後遞迴地排序兩個子序列。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return quickSort(nums)
    }
    
    fun quickSort(nums: IntArray, i1: Int = 0, i2: Int = nums.size - 1): IntArray {
        if(i1 < i2) {
            val pivot = partition(nums, i1, i2)
            quickSort(nums, i1, pivot)
            quickSort(nums, pivot + 1, i2)
        }
        
        return nums
    }

    fun partition(nums: IntArray, i1: Int, i2: Int): Int {

        val pivot = nums[i1]
        var i = i1
        var j = i2

        while(i < j) {
            while(nums[i] <= pivot && i < i2)
                i++

            while(nums[j] > pivot && j > i1)
                j--

            if(i < j) {
                val tmp = nums[i]
                nums[i] = nums[j]
                nums[j] = tmp
            }
        }

        nums[i1] = nums[j]
        nums[j] = pivot

        return j
    }
}

上面的程式碼採用原地 (in-place) 分割

執行結果

RE原因

根據上面的程式碼，我們會發現該程式碼的空間複雜度會根據數列大小而增加，因此我們觀察得該題的空間複雜度可能有限制。

註：Wikipedia指出快速排序會因不同的實作而空間複雜度有所不同

嘗試六：選擇排序 (Selection Sort)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $O(n^2)$
• 最壞時間複雜度：
  $O(n^2)$
• 平均時間複雜度：
  $O(n^2)$

概念

選擇排序會依序將數列內未排序的最小(大)數值排入已排序的數列內，根據大小來決定排序方向性。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return selectionSort(nums)
    }
    
    fun selectionSort(nums: IntArray): IntArray {
        var min: Int
        
        for (i in nums.indices) {
            min = i
            
            for (j in i until nums.size) {
                if (nums[j] < nums[min]) {
                    min = j
                }
            }
            
            if(min != i) {
				val tmp = nums[i]
				nums[i] = nums[min]
				nums[min] = tmp
            }
        }
        
        return nums
    }
}

執行結果

TLE原因

根據演算法的最壞時間複雜度，代入該題的最大上限值

$5\cdot {10}^4$，可以發現最大的迭代次數約為

$2500000000$次，不考慮比較數字所花費的時間，顯然使用該演算法仍不符合效益。

嘗試七：合併排序 (Merge Sort)

簡介

• 實作難易度：困難
• 最佳時間複雜度：
  $O(n\cdot \log (n))$
• 最壞時間複雜度：
  $O(n\cdot \log (n))$
• 平均時間複雜度：
  $O(n\cdot \log (n))$

概念

根據Wikipedia，合併排序採用分治法：

• 分割：遞迴地把當前序列平均分割成兩半。
• 整合：在保持元素順序的同時將上一步得到的子序列整合到一起（合併）。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return mergeSort(nums)
    }
    
    fun mergeSort(nums: IntArray): IntArray {
        val ordered = IntArray(nums.size)
        var i = 2
        while (i < nums.size * 2) {
            for (j in 0 until (nums.size + i - 1) / i) {
                val left = i * j
                val mid = 
                    if (left + i / 2 >= nums.size) nums.size - 1
                    else left + i / 2
                val right = 
                    if (i * (j + 1) - 1 >= nums.size) nums.size - 1
                    else i * (j + 1) - 1
                var start = left
                var l = left
                var m = mid;
                while (l < mid && m <= right)
                    ordered[start++] =
                        if (nums[l] < nums[m]) nums[l++]
                        else nums[m++]
                while (l < mid)
                    ordered[start++] = nums[l++];
                while (m <= right)
                    ordered[start++] = nums[m++];
                System.arraycopy(ordered, left, nums, left, right - left + 1);
            }
            
            i *= 2
        }
        
        return ordered
    }
}

執行結果

備註

由於本題有空間複雜度的限制，所以上面的程式碼採用迭代版本，而非遞迴版本。

嘗試八：堆積排序 (Heap Sort)

簡介

• 實作難易度：中等
• 最佳時間複雜度：
  $O(n\cdot \log (n))$
• 最壞時間複雜度：
  $O(n\cdot \log (n))$
• 平均時間複雜度：
  $O(n\cdot \log (n))$

概念

根據Wikipedia，堆積排序是指利用堆積這種資料結構所設計的一種排序演算法。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return heapSort(nums)
    }
    
    fun heapSort(nums: IntArray): IntArray {
        for (i in (nums.size / 2 - 1) downTo 0)
            maxHeapify(nums, i, nums.size - 1);
        for (i in (nums.size - 1) downTo 1) {
            nums.swap(0, i);
            maxHeapify(nums, 0, i - 1);
        }
        return nums
    }
    
    fun maxHeapify(nums: IntArray, i1: Int, i2: Int) {
        var dad = i1
        var son = dad * 2 + 1
        
        while (son <= i2) {
            if (son + 1 <= i2 && nums[son] < nums[son + 1]) son++;
            if (nums[dad] > nums[son]) return;
            else {
                nums.swap(dad, son);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    fun IntArray.swap(i1: Int, i2: Int) {
        val tmp = this[i1]
        this[i1] = this[i2]
        this[i2] = tmp
    }
}

執行結果

嘗試九：計數排序 (Counting Sort)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $O(n+k)$
• 最壞時間複雜度：
  $O(n+k)$
• 平均時間複雜度：
  $O(n+k)$

概念

根據Wikipedia，計數排序使用一個額外的陣列

$C$，其中第

$i$個元素是待排序陣列

$A$中值等於

$i$的元素的個數。然後根據陣列

$C$來將

$A$中的元素排到正確的位置。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return countingSort(nums)
    }
    
    fun countingSort(nums: IntArray): IntArray {
        val counted = hashMapOf<Int, Int>()
        val ordered = IntArray(nums.size)
        
        for (i in nums.indices) {
            val j = nums[i]
            if (counted.containsKey(j)) counted.put(j, counted[j]!! + 1)
            else counted.put(j, 1)
        }
        
        var i = 0
        for ((k, v) in counted.toSortedMap()) {
            var vtmp = v
            while (vtmp > 0) {
                ordered[i++] = k
                vtmp--
            }
        }
        
        return ordered
    }
}

執行結果

嘗試十：鴿巢排序 (Pigeonhole Sort)

簡介

• 實作難易度：簡單
• 最佳時間複雜度：
  $O(n)$
• 最壞時間複雜度：
  $O(N+n)$
• 平均時間複雜度：
  $O(N+n)$

概念

根據Wikipedia，計數排序是一種時間複雜度為

$O(n)$且在不可避免遍歷每一個元素並且排序的情況下效率最好的一種排序演算法。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return pigeonholeSort(nums)
    }
    
    fun pigeonholeSort(nums: IntArray): IntArray {
        var min = nums.first()!!
        var max = nums.first()!!
        
        for (i in nums.indices) {
            if(nums[i] > max)
                max = nums[i]
            if(nums[i] < min)
                min = nums[i]
        }
        
        val phole = IntArray(max - min + 1)
  
        for(i in nums.indices)
            phole[nums[i] - min]++
  
        var j = 0
        for (i in phole.indices)
            while (phole[i]-- > 0)
                nums[j++] = i + min
        
        return nums
    }
}

執行結果

嘗試十一：閃電排序 (Flash Sort)

簡介

• 實作難易度：中等至困難
• 最佳時間複雜度：
  $O(N)$
• 最壞時間複雜度：
  $O(N^2)$
• 平均時間複雜度：
  $\approx O(N)$

概念

閃電排序是桶排序(Bucket Sort)的優化版，主要的優化有：

• 減少多餘的bucket創建，從而減少記憶體使用
• bucket數量由待排序數列的長度決定

元素會藉由下式決定期望放入的bucket：

$K(A_i)=1+INT((m-1)\cdot \frac{A_i-A_{max}}{A_{max}-A_{min}})$

需要注意的是分母

$A_{max}-A_{min}$有可能為0（若max和min的初始化皆為0），而此式的成立會取決於編譯器對於IEEE 754的實作而有所不同。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return flashSort(nums)
    }
    
    fun flashSort(nums: IntArray): IntArray {
        var min = nums.first()!!
        var max = nums.first()!!
        
        for (i in nums.indices) {
            if(nums[i] > max)
                max = nums[i]
            if(nums[i] < min)
                min = nums[i]
        }
        
        val buckets = arrayOfNulls<MutableList<Int>>(nums.size)
        
        for (i in nums.indices) {
            val e = nums[i]
            val idx = (nums.size - 1) * ((e - min).toDouble() / (max - min)).toInt()
            var bucket = buckets[idx]
            
            if (bucket == null) {
                bucket = mutableListOf()
                buckets[idx] = bucket
            }
            
            bucket.add(e)
        }
        
        val output = IntArray(nums.size)
        var cnt = 0
        
        for (i in nums.indices) {
            val bucket = buckets[i]
            
            if (bucket != null) {
                val segment = pigeonHoleSort(bucket.toIntArray())
                for (j in segment.indices) {
                    output[cnt++] = segment[j]
                }
            }
        }
        
        return output
    }
    
    fun pigeonHoleSort(nums: IntArray): IntArray {
        var min = nums.first()!!
        var max = nums.first()!!
        
        for (i in nums.indices) {
            if(nums[i] > max)
                max = nums[i]
            if(nums[i] < min)
                min = nums[i]
        }
        
        val phole = IntArray(max - min + 1)
  
        for(i in nums.indices)
            phole[nums[i] - min]++
  
        var j = 0
        for (i in phole.indices)
            while (phole[i]-- > 0)
                nums[j++] = i + min
        
        return nums
    }
}

上面的程式碼的最終排序使用鴿巢排序。

執行結果

嘗試十二：基數排序 (Radix Sort)

簡介

• 實作難易度：中等至困難
• 最佳時間複雜度：
  $O(N)$
• 最壞時間複雜度：
  $O(k\cdot N)$
• 平均時間複雜度：
  $O(N)$

概念

基數排序將數列中每個數字按位元數切割成不同的數字，然後按每個位數分別比較，藉此達成排序的目的。基數排序的實作方式可分為LSD（Least significant digital）及MSD（Most significant digital），其差異在於排序的開始端。

import kotlin.math.abs
import kotlin.math.log10
import kotlin.math.pow

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        return radixSort(nums)
    }

    fun radixSort(nums: IntArray): IntArray {
        val k = maxDigit(nums)
        
        for (i in 0 until k) {
            val buckets = arrayOfNulls<MutableList<Int>>(20)
            
            for (j in nums.indices) {
                val digit = digit(nums[j], i)
                if (buckets[digit + 10] == null)
                    buckets[digit + 10] = mutableListOf()
                buckets[digit + 10]!!.add(nums[j])
            }
            var numsIdx = 0
            for (bucket in buckets) {
                if (bucket == null) continue
                for (j in bucket.indices)
                    nums[numsIdx++] = bucket[j]
            }
        }
        return nums
    }

    fun digit(num: Int, place: Int): Int = 
        (num / 10.0.pow(place)).toInt() % 10

    fun maxDigit(nums: IntArray): Int {
        var maxDigits = 0
        for (number in nums)
            maxDigits = maxDigits.coerceAtLeast(digitCount(number))
        return maxDigits
    }

    fun digitCount(number: Int): Int = 
        log10(abs(number).toDouble()).toInt() + 1
}

執行結果