破題

• 假設：陣列的長度為 。
• 題意：這題是希望我們找出一個整數陣列中第 大的數字。

方法一：計數排序 (Counting Sort)

解題思路

1. 首先，我們遍歷整個陣列，找出最小和最大的數字。
2. 然後，我們宣告一個計數陣列，其大小為最大數字和最小數字之間的範圍加一。每個元素的初始值都設為 0。
3. 再次遍歷原始陣列，對每個數字出現的次數進行計數。計數的方式是將該數字減去最小值，然後在計數陣列中對應的位置加一。
4. 從計數陣列的尾端開始向前遍歷，直到找到第 大的數字。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：4886)

程式

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        var min = 0
        var max = 0
        nums.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
        val counts = IntArray(max - min + 1) { 0 }
        nums.forEach {
            counts[it - min]++
        }
        var remains = k
        var ans = nums[0]
        for (i in counts.size - 1 downTo 0) {
            val count = counts[i]
            if (remains - count > 0) {
                remains -= count
            } else {
                ans = i + min
                break
            }
        }
        return ans
    }
}

複雜度分析

• 時間複雜度:
  ，其中 為原始陣列的大小。我們需要遍歷原始陣列兩次，一次是找出最大和最小值，另一次是進行計數。然後我們還需要遍歷計數陣列來找出第 大的數字。但由於我們只遍歷每個陣列一次，所以時間複雜度為 。

• 空間複雜度:
  ，其中 為最大和最小值之間的範圍。我們需要宣告一個大小為 的計數陣列來存儲每個數字出現的次數。因此，空間複雜度為 。
  但如果 遠大於 ，則空間複雜度可能會成為問題。在這種情況下，我們可能需要使用其他方法來解決這個問題。例如，我們可以使用「快速排序 (Quick Sort)」的演算法來在 時間內找到第 大的元素，這樣只需要常數量級的空間。

　更多演算法題解，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：4886)