前往
大廳
主題

LeetCode - 2028. Find Missing Observations 解題心得

Not In My Back Yard | 2022-03-21 00:00:09 | 巴幣 100 | 人氣 200

題目連結:


題目意譯:
你有 n + m 次觀察擲骰子的點數,其中骰子每面編號為 1 ~ 6。其中 n 次觀察的數值消失了,你只留下了 m 次個觀察。不幸中的大幸是,你有把 n + m 次擲骰子的點數和平均算出來。

你被給定一長度為 m 的整數陣列 rolls,其中 rolls[i] 代表第 i 觀察中的點數。你同時也被給定兩整數 mean 和 n。

回傳一長度為 n 的陣列包含著那些消失的觀察數據使得 n + m 次擲骰子的數值總和之平均恰好為 mean。如果有多個合法的答案,則回傳任意一個。如果無解,則回傳空陣列。

一個 k 個數字之集合的平均值為所有數字總和除以 k。

注意 mean 為一整數,因此 n + m 次擲骰子的點數總和應可被 n + m 整除。

限制:
m == rolls.length
1 ≦ n, m ≦ 10 ^ 5
1 ≦ rolls[i], mean ≦ 6



範例測資:
範例 1:
輸入: rolls = [3,2,4,3], mean = 4, n = 2
輸出: [6,6]
解釋: n + m 次擲骰子的平均為 (3 + 2 + 4 + 3 + 6 + 6) ÷ 6 = 4。

範例 2:
輸入: rolls = [1,5,6], mean = 3, n = 4
輸出: [2,3,2,2]
解釋: n + m 次擲骰子的平均為 (1 + 5 + 6 + 2 + 3 + 2 + 2) ÷ 7 = 3。

範例 3:
輸入: rolls = [1,2,3,4], mean = 6, n = 4
輸出: []
解釋: 不論 4 次消失的觀察數據為何都不可能使平均等於 6。


解題思維:
首先我們計算一下我們還需要多少的點數——即把 mean 乘以 (n + m) 後減去 rolls 中所有數字的總和,得一數 R。因為我們尚有 n 次的骰子,每次的點數至少為 1,因此我們把 R 再減去 n,得 R'。

接著判斷 R' 是否小於 0 或是大於 5n。如果是前者則代表就算我們使 n 次骰子都是 1,n + m 次總和依舊會超過要求;類似地,如果是後者則代表就算我們使 n 次骰子都是點數 6,也無法使 n + m 次的總和到達要求。這兩個情況下,我們是不可能達成要求的,因此回傳空陣列。

如果上述兩種情況都沒發生,則我們可以把 n 次觀察的數據湊出來:
先將 R' 除以 5,得 X 餘 r。X 代表我們需要 X 個 6,因此結果陣列中先放入 X 個 6,剩下先放 n - X 個 1。

接著 r ≠ 0 的話,則代表我們還需要再多點數 r,而這個可以直接加到最後一次的骰子之中。

因此我們造出來的陣列會像是 [6, 6, 6, ……, 1, 1, ……, K],其中 K 為 1 ~ 5 的某個數字。可以看到這樣子造必定會使平均符合要求,因此這個陣列即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作