切換
舊版
前往
大廳
主題

LeetCode - 219. Contains Duplicate II 解題心得

Not In My Back Yard | 2020-09-13 00:00:07 | 巴幣 2 | 人氣 477

題目連結:


題目意譯:
給定一整數陣列 nums 以及一整數 k ,找到陣列中是否存在兩個索引值 i 和 j ,滿足 nums[i] = nums[j] 且 i 與 j 差值之絕對值不超過 k 。



範例測資:
範例 1:
輸入: nums = [1,2,3,1],k = 3
輸出: true

範例 2:
輸入: nums = [1,0,1,1],k = 1
輸出: true

範例 3:
輸入: nums = [1,2,3,1,2,3],k = 2
輸出: false


解題思維:
將原陣列 nums 裡的所有值與它們的索引值綁在一起(可以自己寫資料結構,或是用內建的資料型態儲存),然後先依據值的大小由小排到大(大到小也行),再根據索引值的大小再根據大小排(同樣地,小到大或大到小皆可)。

這樣子一來,值相同的數字就會排在一起,而且按照索引值排序。所以只要掃過一次,每次跟該元素的前一個元素做比較。如果值一樣,且索引值之差 ≦ k,則即符合題目的要求,回傳真(True);反之,如果掃完之後,沒有遇到任何符合的情況發生,則回傳假(False)。




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

創作回應

更多創作