python數組中的 k-diff 數對例題解析
一、題目描述
題目內容:
題目示例:
題目解析:
1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107
二、思路分析
我們拿到本題,讀取題意要求在一組整數數組中,求出差值為k的數對對數k-diff。在思考如何解答該題之前,需要明確如下幾點細節:
- nums數組元素都是整數
- 索引位置i與位置j,不能相等
- k-diff數對關系:nums[i] – nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] – k = nums[j]
- k-diff數對,存在相同數對情況,但結果隻取1次
因此,我們的對題目中進行詳細瞭解瞭,因為會排除重復的數對,我們很容易想哈希表來構建
方法一:構建哈希表
根據上述思路,我們使用python代碼能快速實現,代碼如下:
class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ ans = set() numset = set() for num in nums: if num - k in numset: ans.add(num-k) if num + k in numset: ans.add(num) numset.add(num) return len(ans)
- 數對中重復場景如示例一中差值為k=1,(1,3) & (3,1)視為一種情況,則要定義兩個哈希表來儲存
- 哈希表可以通過字典k-value或者集合set(),本題無需考慮索引關系定義ans,numset兩個集合
- 當 nums[i] > nums[j],則nums[j] = nums[i] – k在numset中,取最小的那一個則ans.add(nums[i]-k),
- 當 nuns[i] < nums[j],則nums[j] = nums[i] + k 在numset中,取較小的那一個則ans.add(nums[i])
方法二:雙指針
根據上述思路,使用python代碼實現,代碼如下:
class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort() ans = 0 j = 0 for i in range(len(nums)): if i == 0 or nums[i] != nums[i-1]: while j < len(nums) and (nums[j] < nums[i] + k or j <= i): j +=1 if j < len(nums) and nums[j] == nums[i] + k: ans +=1 return ans
- 首先對nums數組中的元素按照從低到高的順序排列
- 在遞增的數組中,由於雙指針 i!=j,因此i指針一定是小於j的
- 枚舉查找的判斷的條件 nums[j] < nums[i]+k,指針j則往後移動
- 當nums[j] = nums[i] + k 時,則對數次數+1
三、總結
本題可以使用哈希方法要使用兩個哈希表,屬於犧牲空間換取效率。雙指針方法,雖然沒有用額外的空間,但是速度較於方法一慢一點。
我們用第一種方法,AC提交記錄如下:
- 時間復雜度O(n),n為nums長度
- 空間復雜度O(n),需要使用哈希表,n為nums長度
到此這篇關於python數組中的 k-diff 數對例題解析的文章就介紹到這瞭,更多相關python k-diff 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java算法練習題,每天進步一點點(2)
- go語言的四數相加等於指定數算法
- python刪除列表中特定元素的幾種方法
- C++實現LeetCode(16.最近三數之和)
- C++實現LeetCode(三數之和)