<h1>
- [O] 34. Find First and Last Position of Element in Sorted Array
</h1>
<h2>
題目
</h2>
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
---
<h2>
思路
</h2>
第一眼看到O(log n)直覺使用Binary Search(很久以前刷過這題)
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
我的思路是先用Binary Search 找出target，然後再往target 的左右分別進行Binary Search，例如這題中如果我先找到index為3的8，我會分別再對[5,7,7]及[8,10]做Binary Search。
```python=
class Solution(object):
def binarySearch(self,nums,target,start,end,ans):
if end<start:
return
mid=(end+start)/2
if nums[mid]>target:
end=mid-1
self.binarySearch(nums,target,start,mid-1,ans)
elif nums[mid]<target:
start=mid+1;
self.binarySearch(nums,target,mid+1,end,ans)
else:
if mid<ans[0]:
ans[0]=mid
if mid>ans[1]:
ans[1]=mid
self.binarySearch(nums,target,mid+1,end,ans)
self.binarySearch(nums,target,start,mid-1,ans)
def searchRange(self, nums, target):
start=0
end=len(nums)-1
ans=[100000,-1]
if len(nums)==0:
return [-1,-1]
self.binarySearch(nums,target,start,end,ans)
if ans[0]==100000:
ans[0]=-1
return ans
```
Discussion 中找到比較乾淨的寫法：
用兩個function分別去找最左側和最右側的target
```python=
def searchRange(self, A, target):
lmost = self.leftsearch(A,target)
rmost = self.rightsearch(A,target)
return[lmost,rmost]
def leftsearch(self,A,tar):
l = 0
r = len(A)-1
tarI = -1#target index
while l <= r:
mid = (l+r)/2
if A[mid] > tar:
r = mid - 1
elif A[mid] < tar:
l = mid + 1
else:
tarI = mid
r = mid - 1
return tarI
def rightsearch(self,A,tar):
l = 0
r = len(A)-1
tarI = -1
while l <= r:
mid = (l+r)/2
if A[mid] > tar:
r = mid -1
elif A[mid] <tar:
l = mid + 1
else:
tarI = mid
l = mid+1
return tarI
```
<h1>
- [X]1539. Kth Missing Positive Number
</h1>
<h2>
題目
</h2>
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
---
<h2>
思路
</h2>
暴力解，arr中每有一個<=k的數字，最後的答案就會被往後推->O(N)。
```python=
class Solution(object):
def findKthPositive(self, arr, k):
ans=k
for i in range(0,len(arr),1):
if arr[i]<=ans:
ans=ans+1
return ans
"""
:type arr: List[int]
:type k: int
:rtype: int
"""
```
Discussion O(log N)解法
i.e.: [2, 3, 4, 7, 11, 12] and k = 5.
創造一個新的Array B。B = [2 - 1, 3 - 2, 4 - 3, 7 - 4, 11 - 5, 12 - 6] = [1, 1, 1, 3, 6, 6].
B代表消失的正整數個數 例如在B[2]->我們有2,3,4缺 1->B[2]=1。
因為原始Array是嚴格遞增->如果所有數字都在會從1,2,3,4.....一直排下去。
我們只要從B Array中找出<k的index，就代表有index+1個數字存在->答案就是k+index+1。
```python!
class Solution:
def findKthPositive(self, arr, k):
beg, end = 0, len(arr)
while beg < end:
mid = (beg + end) // 2
if arr[mid] - mid - 1 < k:
beg = mid + 1
else:
end = mid
return end + k
```
<h1>
- [X]378.Kth Smallest Element in a Sorted Matrix
</h1>
<h2>
題目
</h2>
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
ex:
```
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
```
---
<h2>
思路
</h2>
暴力解->將所有matrix中的elements丟到priority queue取出第k個。
```python!
class Solution(object):
def kthSmallest(self, matrix, k):
sortM=[]
for i in range(0,len(matrix),1):
for j in range(0,len(matrix[0]),1):
heappush(sortM,matrix[i][j])
for j in range(0,k-1,1):
heappop(sortM)
return heappop(sortM)
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
```
---
<h2>
Discussion裡的優化方法
</h2>
* Idea
1. We binary search to find the smallest ans in range [minOfMatrix..maxOfMatrix] as long as countLessOrEqual(ans) >= k, where countLessOrEqual(x) is the number of elements less than or equal to x.
2. Why ans must be as smallest as possible?
3. Why countLessOrEqual(ans) >= k but not countLessOrEqual(ans) == k?
* Algorithm
1.Start with left = minOfMatrix = matrix[0][0] and right = maxOfMatrix = matrix[n-1][n-1].
2.Find the mid of the left and the right. This middle number is NOT necessarily an element in the matrix.
3.If countLessOrEqual(mid) >= k, we keep current ans = mid and try to find smaller value by searching in the left side. Otherwise, we search in the right side.
4.Since ans is the smallest value which countLessOrEqual(ans) >= k, so it's the k th smallest element in the matrix.
---
```python!
class Solution(object):
def countLessThan(self,matrix,target):
row=0
column=len(matrix[0])-1
rowSize=len(matrix)
columnSize=len(matrix[0])
num=0
while row>=0 and row<rowSize and column>=0 and column<columnSize:
if matrix[row][column]<=target:
num+=(column+1)
row+=1;
else:
column-=1;
return num
def kthSmallest(self, matrix, k):
left=matrix[0][0]
right=matrix[len(matrix)-1][len(matrix[0])-1]
ans=0
while left<=right:
mid=(left+right)/2
if self.countLessThan(matrix,mid)>=k:
right=mid-1
ans=mid
else:
left=mid+1
return ans
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
```
<h1>
- [Ｏ]852-Peak Index in a Mountain Array
</h1>
<h2>
題目
</h2>
An array arr a mountain if the following properties hold:
arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].
You must solve it in O(log(arr.length)) time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
---
<h2>
思路
</h2>
Binary Search找peak
```python!
class Solution(object):
def peakIndexInMountainArray(self, arr):
start=0
end=len(arr)-1
while start<end:
mid=(start+end)/2
if arr[mid]<arr[mid+1]:
start=mid+1
else:
end=mid
return start
"""
:type arr: List[int]
:rtype: int
"""
```
<h1>
- [X]41. Arranging Coins
</h1>
<h2>
題目
</h2>
You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.
```
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.
```
---
<h2>
思路
</h2>
暴力解，從1~n中找到符合(1+n)*n/2>=硬幣數的n。
```python!
class Solution(object):
def arrangeCoins(self, n):
target=n
for i in xrange(1,n+1,1):
if (i**2+i)/2>target:
return i-1
if (i**2+i)/2==target:
return i
return -1
"""
:type n: int
:rtype: int
"""
```
<h2>
優化
</h2>
利用Binary Search加快搜尋的速度。
```python!
class Solution(object):
def arrangeCoins(self, n):
if n==1:
return 1
start=1
end=n
while start<end:
mid=(start+end)/2
if (mid+1)*mid/2<=n:
start=mid+1
else:
end=mid
return start-1
```
<h2>
再優化
</h2>
直接用數學解。
k(k+1)≤2N
(k+1/2)^2-1/4<=2N
k=(2N+1/4)^0.5-1/2
```python!
class Solution(object):
def arrangeCoins(self, n):
return (int)((2*n+0.25)**0.5-0.5)
"""
:type n: int
:rtype: int
"""
```
<h1>
- [O]1482. Minimum Number of Days to Make m Bouquets
</h1>
<h2>
題目
</h2>
You are given an integer array bloomDay, an integer m and an integer k.
You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
**ex:**
```
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
```
---
<h2>
思路
</h2>
花期介於min(bloomDay)與max(bloomDay)之間，利用Binary Search去找可以滿足m束花的花期，若找到滿足的花期，將上界設為這個花期，盡量找短的花期。
```python!
class Solution(object):
def minDays(self, bloomDay, m, k):
if (m*k)>len(bloomDay):
return -1
maxDay=max(bloomDay)
minDay=min(bloomDay)
while minDay<maxDay:
mid=(minDay+maxDay)/2
flowerNum=0
bouquetsNum=0
for i in bloomDay:
if i<=mid:
flowerNum+=1
else:
flowerNum=0
if flowerNum==k:
bouquetsNum+=1
flowerNum=0
if bouquetsNum==m:
maxDay=mid
break
else:
minDay=mid+1
return minDay
"""
:type bloomDay: List[int]
:type m: int
:type k: int
:rtype: int
"""
```
<h1>
1855.Maximum Distance Between a Pair of Values
</h1>
Sign in with Wallet
Connect another wallet