題目連結:
題目意譯:
你被給定兩字串陣列 positive_feedback 和 negative_feedback,其分別包含著正面以及負面的意見回饋之字詞。注意到,沒有任何字詞同時是正面和負面的。
一開始每一位學生都是 0 分。當學生在意見回饋報告中每收到一個正面字詞,分數便會增加 3;而每收到一個負面字詞則分數減去 1。
你被給定 n 個以一個索引值從 0 開始的字串陣列 report 表示之意見回饋報告以及一個索引值從 0 開始的整數陣列 student_id,其中 student_id[i] 代表著收到 report[i] 這份意見回饋報告的學生之 ID。每一位學生的 ID 是獨一無二的。
給定一整數 k,回傳根據學生們的分數排序後排名前 k 高者。為了保險起見,如果有多位學生有著相同的分數,則有著較小 ID 值者排名較高。
限制:
1 ≦ positive_feedback.length, negative_feedback.length ≦ 10 ^ 4
1 ≦ positive_feedback[i].length, negative_feedback[j].length ≦ 100
positive_feedback[i] 和 negative_feedback[j] 都由小寫英文字母組成。
沒有字詞同時出現於 positive_feedback 和 negative_feedback 之中。
n == report.length == student_id.length
1 ≦ n ≦ 10 ^ 4
report[i] 由小寫英文字母以及空白 ' ' 所組成。
在 report[i] 中每個字詞之間都有一個空白。
1 ≦ report[i].length ≦ 100
1 ≦ student_id[i] ≦ 10 ^ 9
student_id[i] 中的數值彼此相異。
1 ≦ k ≦ n
範例測資:
範例 1:
輸入: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
輸出: [1,2]
解釋:
兩位學生都有著 1 個正面回饋和 3 分。但由於學生 1 有著更小的 ID 值,因此他的排名比較高。
範例 2:
輸入: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
輸出: [2,1]
解釋:
- ID 值是 1 的學生有著 1 正面回饋以及 1 個負面回饋,所以他有 3 - 1 = 2 分。
- ID 值是 1 的學生有著 1 正面回饋,所以他有 3 分。
由於學生 2 有更多分數,因此我們回傳 [2,1]。
解題思維:
直接計算出每一位學生的分數,而為了處理學生 ID 與其對應分數值的資料,我們可以使用雜湊表(Hash Table)來儲存。
得到所有學生的分數之後,接著就跟一般的自定義排序(如
這題)一樣把分數和 ID 綁在一起形成一個結構(Struct)。最後根據題目定義的規則排序後取前 k 個學生的 ID 即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。