Re: [閒聊] 每日leetcode
2053. Kth Distinct String in an Array
## 思路
用Counter計算string出現次數
再for loop找第k個Counter[s] == 1 的字串
## Complexity
Time: O(N)
Space: O(N)
## Code
```python
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
counter = Counter(arr)
for s in arr:
if counter[s] == 1:
k -= 1
if k == 0:
return s
return ''
```
--
順便從Leetcode 75找一題medium來寫
1679. Max Number of K-Sum Pairs
找出相加為k的pairs數
其實就是Two Sum題型
HashTable
Time: O(N), Space(N)
```python
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
counter = Counter()
ans = 0
for num in nums:
if counter[k-num]:
counter[k-num] -= 1
ans += 1
else:
counter[num] += 1
return ans
```
Sort + TwoPointer
Time: O(NlogN), Space: O(1)
```python
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
nums.sort()
ans = 0
left, right = 0, len(nums)-1
while left < right:
two_sum = nums[left] + nums[right]
if two_sum > k:
right -= 1
elif two_sum < k:
left += 1
else:
left += 1
right -= 1
ans += 1
return ans
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.169 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722841011.A.DF6.html
討論串 (同標題文章)
完整討論串 (本文為第 640 之 1548 篇)：