Bài toán
Link đến bài toán: 1095. Find in Mountain Array
Phân tích
Nếu tạm bỏ qua constraint
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Thì bài toán này đơn giản có thể giải bằng cách gọi MountainArray.get
cho đến khi tìm được giá trị cần tìm.
Độ phức tạp của giải thuật là O(n)
.
Nhìn vào dữ kiện của bài toán, ta thấy rằng mảng mountainArr
là một mảng tăng dần đến một điểm peak
rồi giảm dần.
Làm thế nào để tìm một phần tử trong một mảng đã được sắp xếp? Binary Search.
Tuy nhiên, ta chưa thể áp dụng binary search trực tiếp vào bài toán này được vì mảng mountainArr
chưa phải hoàn toàn được sắp xếp.
Ta cần tìm một điểm chia mảng mountainArr
thành hai mảng con được sắp xếp tăng dần và giảm dần. Ta sẽ gọi điểm chia này là peak
.
Nhận thấy rằng, với 0 <= i < peak
, mountainArr[i] < mountainArr[i + 1]
và với peak < i < mountainArr.length() - 1
,
mountainArr[i] > mountainArr[i + 1]
.
Ta có thể áp dụng binary search để tìm peak
với độ phức tạp O(log(n))
.
Sau khi tìm được peak
, ta có thể áp dụng binary search để tìm giá trị cần tìm trong mảng con được sắp xếp tăng dần và giảm dần.
Giải thuật
- Tìm
peak
bằngbinary search
:- Nếu
mountainArr[mid] < mountainArr[mid + 1]
thìpeak
nằm ở bên phảimid
. - Nếu
mountainArr[mid] > mountainArr[mid + 1]
thìpeak
nằm ở bên tráimid
. - Lặp lại bước 1 cho đến khi
left == right
.
- Nếu
- Áp dụng
binary search
cho mảng tăng dần trên đoạn[0, peak]
. - Nếu không tìm thấy ở bước 2, áp dụng
binary search
mảng giảm dần trên đoạn[peak + 1, mountainArr.length() - 1]
.
Độ phức tạp của giải thuật là O(log(n))
.
Code
func findInMountainArray(target int, mountainArr *MountainArray) int {
n := mountainArr.length()
peakIndex := findPeak(mountainArr, 0, n-1)
peakValue := mountainArr.get(peakIndex)
if target == peakValue {
return peakIndex
}
searchLeft := binarySearch(mountainArr, target, 0, peakIndex-1, true)
if searchLeft != -1 {
return searchLeft
}
return binarySearch(mountainArr, target, peakIndex+1, n-1, false)
}
func findPeak(mountainArr *MountainArray, l, r int) int {
for l < r {
mid := l + (r-l)/2
if mountainArr.get(mid) < mountainArr.get(mid+1) {
l = mid + 1
} else {
r = mid
}
}
return l
}
func binarySearch(mountainArr *MountainArray, target, l, r int, asc bool) int {
if asc {
for l <= r {
mid := l + (r-l)/2
midValue := mountainArr.get(mid)
if midValue == target {
return mid
} else if midValue < target {
l = mid + 1
} else {
r = mid - 1
}
}
} else {
for l <= r {
mid := l + (r-l)/2
midValue := mountainArr.get(mid)
if midValue == target {
return mid
} else if midValue < target {
r = mid - 1
} else {
l = mid + 1
}
}
}
return -1
}