⋯⋯幸好並不是,她問我剛剛送出的答案是不是之前提到用時比較少的答案。
「對,因為這個解法只用了一層迴圈,用在計算目前數字的總和nums.sum()
函式裡面,演算法複雜度是O(n)。之前妳兩層迴圈的算法,複雜度是O(n^2)。哦,n是陣列大小,O的發音是Big O,說是上限,其實就是指最糟的情形。買東西我們都會定個預算上限不是嗎?就是那種感覺。」
為了確認效能,我曾經查找nums.sum()
函式執行的程式碼,發現很普通,就是平常算加總的寫法。
public fun IntArray.sum(): Int {
var sum: Int = 0
for (element in this) {
sum += element
}
return sum
}
學妹歪頭想了一下:「哦,這種簡化方式很像國中時流行的真假金幣問題,就是那個要從好幾袋金幣中找出一袋假幣,只能秤一次的那個。」
「對對,像這種可以把問題簡化到和袋子數量無關的複雜度O(1)是最理想的,所以當初發現連續數字加總可以用頭尾相加乘以數量一半的數學家高斯很厲害呢。」我還滿喜歡數學的,可惜也只是普通程度的擅長。
思緒不自覺地飄遠,直到學妹叫我,我才回過神來:「啊,不過,在有時間懲罰的情形下,還是先把答案寫出來,有多餘時間再去思考更好的答案吧。」
「呃,學姊,那個⋯⋯」學妹說話突然開始支支吾吾。「其實,當初打開題目的時候螢幕有閃過一個視窗,現在回想起來,應該是叫我們在十分鐘內送出答案。」
「原來如此,謝謝妳告訴我。」也沒什麼好意外的,平常開程式的時候我也常略過提示,雖然這次是要命的提示。「以後有什麼線索我們都共享,也許會發現離開房間的線索。」
「嗯,好。那我們繼續解題嗎?但是不知道是不是所有題目都是十分鐘限制⋯⋯」
「十分鐘解出easy的題目還算合理,但是medium和hard就有點懸了。某個有刷題習慣的朋友和我說過,不能在半小時內解決就最好跳過,或是去看其他人的做法,所以我們還是先繼續解easy的題目,妳Kotlin哪塊比較熟悉?」
「哦,因為聽說Kotlin在Collection這塊特別豐富,我買了台灣工程師寫的《Kotlin Collection全方位解析攻略 : 精通原理及實戰,寫出流暢好維護的程式》來看。」
「那妳應該可以應付這題1929. Concatenation of Array,這題要求把陣列巨大化成兩倍。」
class Solution {
fun getConcatenation(nums: IntArray): IntArray {
}
}
「我可以!只要建立一個大小是原本兩倍的新陣列,然後回傳陣列索引取餘數的結果。」她說著啪啪啪的打了出來。
class Solution {
fun getConcatenation(nums: IntArray): IntArray {
return IntArray(nums.size * 2, { nums[it % nums.size] })
}
}
送出之前她又微微調整了答案:「不知道少一個逗號會不會比較加分?」
class Solution {
fun getConcatenation(nums: IntArray): IntArray {
return IntArray(nums.size * 2) { nums[it % nums.size] }
}
}
「這個我也不知道,不過為防萬一,不要直接Submit
,先Run Code
。Run Code
會先跑基本測試,基本測試通過比較保險。」
「好吧。」
基本測試通過,學妹爽快的送出答案。
不知道這次會是什麼獎品,希望不是又來兩碗泡麵。