Find First and Last Position of Element in Sorted Array
Bạn nhận được một danh sách số nguyên nums được sắp xếp theo thứ tự không giảm, nên một giá trị có thể xuất hiện nhiều lần, và một số nguyên target. Hãy trả về một danh sách gồm hai chỉ số, tính từ 0: vị trí đầu tiên và vị trí cuối cùng mà target xuất hiện. Nếu target không có trong danh sách, hãy trả về [-1, -1]. Hãy hướng đến độ phức tạp thời gian O(log n).
Hàm
- numsinteger-array
- danh sách số nguyên đã được sắp xếp, có thể có các giá trị lặp lại
- targetinteger
- giá trị cần tìm
- Trả vềinteger-array
- chỉ số đầu tiên và cuối cùng của target, hoặc [-1, -1] nếu không tìm thấy
Ràng buộc
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsđược sắp xếp theo thứ tự không giảm.
Ví dụ
- Đầu vào
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Đầu ra
- [1, 3]
- Giải thích
- Ba số 5 nằm ở các chỉ số 1, 2 và 3, nên dãy bắt đầu ở chỉ số 1 và kết thúc ở chỉ số 3. Chỉ số 0 chứa số 3 và chỉ số 4 chứa số 8, nên dãy không thể kéo dài hơn.
- Đầu vào
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Đầu ra
- [-1, -1]
- Giải thích
- 7 sẽ nằm giữa 5 ở chỉ số 3 và 8 ở chỉ số 4, nhưng không số nào là 7. Danh sách không có bản sao nào, nên đáp án là
[-1, -1].
Câu hỏi mở rộng
Nếu cùng một danh sách nhận hàng nghìn truy vấn với các mục tiêu khác nhau, liệu duyệt qua danh sách trước một lần có thể giúp mỗi truy vấn nhanh hơn O(log n) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Vì
numsđã được sắp xếp, mọi bản sao củatargetđều nằm cạnh nhau thành một dãy. Bạn cần tìm hai đầu của dãy đó.Tìm một bản sao rồi đi dần ra ngoài có thể tốn
O(n)khi dãy liên tiếp dài. Thay vào đó, hãy sửa đổi tìm kiếm nhị phân để tiếp tục đi sang trái sau khi tìm thấy kết quả khớp: khi đó, nó sẽ dừng ở chỉ số đầu tiên có giá trị lớn hơn hoặc bằng số bạn cần tìm.Viết một hàm trợ giúp trả về chỉ số đầu tiên thỏa mãn
nums[i] ≥ value. Gọi hàm vớitargetđể tìm điểm bắt đầu của dãy, kiểm tra xem giá trị tại đó có phải làtargetkhông, rồi gọi hàm vớitarget + 1: dãy kết thúc ở chỉ số ngay trước đó.
Lời giải
Tìm kiếm nhị phân thông thường dừng ở bản sao bất kỳ của target mà nó gặp, và bản sao đó có thể nằm ở bất cứ đâu trong dãy liên tiếp. Thay vào đó, hãy tìm cận dưới: chỉ số đầu tiên có giá trị lớn hơn hoặc bằng một số cho trước. Cận dưới của target và target + 1 cho ta cả hai đầu của dãy liên tiếp trong O(log n).
Quét toàn bộ danh sách
Ý tưởng
Duyệt qua danh sách một lần. Chỉ số đầu tiên chứa target là điểm bắt đầu, còn chỉ số cuối cùng là điểm kết thúc. Nếu target không xuất hiện, cả hai đều giữ giá trị -1.
Cách này áp dụng được với mọi danh sách, đã sắp xếp hay chưa, và đó cũng là nhược điểm của nó: cách này đọc tất cả n giá trị. Với danh sách có 10^4 giá trị, cách này cần 10.000 phép so sánh, trong khi khoảng 28 phép là đủ.
Thuật toán
- Đặt
first = last = -1. - Với mỗi chỉ số
i, nếunums[i]bằngtarget, hãy đặtfirst = ikhifirstvẫn là-1, rồi đặtlast = i. - Trả về
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]Tìm một bản sao, rồi mở rộng
Ý tưởng
Tìm kiếm nhị phân để tìm một chỉ số bất kỳ có giá trị target. Danh sách đã được sắp xếp, nên mọi bản sao đều nằm liền nhau quanh chỉ số đó: đi sang trái và phải khi phần tử liền kề vẫn là target.
Phép tìm kiếm tốn O(log n), còn mỗi bản sao cần đi thêm một bước, tổng cộng là k bước. Khi phần lớn danh sách là target, chẳng hạn có 10^4 bản sao, bước đi sẽ đọc mọi giá trị và bạn lại phải quét tuyến tính.
Thuật toán
- Tìm kiếm nhị phân để tìm bất kỳ chỉ số
foundnào thỏa mãnnums[found] == target. - Nếu không có, trả về
[-1, -1]. - Di chuyển
firstsang trái từfoundkhi giá trị phía trước nó bằngtarget. - Di chuyển
lastsang phải từfoundkhi giá trị phía sau nó bằngtarget. - Trả về
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]Hai phép tìm kiếm nhị phân cận dưới
Ý tưởng
Hãy đặt một câu hỏi khác: chỉ số đầu tiên có giá trị lớn hơn hoặc bằng value là bao nhiêu? Chỉ số đó là cận dưới, hoặc là n nếu không có giá trị nào thỏa mãn. Duy trì một khoảng nửa mở [lo, hi) luôn chứa chỉ số đó. Nếu nums[mid] < value, thì mid và mọi chỉ số trước nó đều có giá trị quá nhỏ. Nếu không, mid thỏa mãn, nhưng một chỉ số trước đó cũng có thể thỏa mãn, nên mid vẫn nằm trong khoảng và trở thành hi mới. Vòng lặp không bao giờ dừng sớm khi tìm thấy giá trị khớp.
Cận dưới của target là vị trí bắt đầu đoạn có giá trị bằng nó. Các giá trị là số nguyên, nên giá trị đầu tiên lớn hơn target nằm tại cận dưới của target + 1, và đoạn kết thúc ở chỉ số ngay trước đó một đơn vị. Trong ví dụ đầu tiên, cận dưới của 5 là 1 và cận dưới của 6 là 4, vị trí có giá trị 8: đoạn này là [1, 3]. Hai lần tìm kiếm mất khoảng 28 bước với 10^4 giá trị, bất kể độ dài của đoạn.
Thuật toán
- Viết hàm
lowerBound(value): bắt đầu vớilo = 0,hi = n; khilo < hi, nếunums[mid] < valuethì đặtlo = mid + 1, nếu không thì đặthi = mid; trả vềlo. - Đặt
first = lowerBound(target). - Nếu
first == nhoặcnums[first] != target, trả về[-1, -1]. - Đặt
last = lowerBound(target + 1) - 1và trả về[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
Lỗi thường gặp và trường hợp biên
- Trả về ngay khi
nums[mid] == target. Chỉ số đó có thể nằm ở bất kỳ vị trí nào trong dãy: trong[3, 5, 5, 5, 8], vị trí giữa đầu tiên là chỉ số 2, không nằm ở đầu hay cuối. - Ghi
hi = mid - 1trong phép tìm cận dưới khinums[mid] ≥ value. Cách này loại bỏmid, trong khi đó có thể là đáp án. - Đọc
nums[first]mà không kiểm trafirst < n. Khitargetlớn hơn mọi giá trị, chẳng hạn như 13 trong các ví dụ, cận dưới làn, tức vị trí ngay sau phần tử cuối. - Quên điều chỉnh chỉ số trong Lua và R. Danh sách của hai ngôn ngữ này bắt đầu từ 1, vì vậy hãy trừ 1 ở cả hai vị trí.
Câu hỏi thường gặp3
Độ phức tạp thời gian khi tìm vị trí đầu tiên và cuối cùng là gì?
Độ phức tạp thời gian O(log n) và độ phức tạp không gian O(1), với hai lần tìm kiếm nhị phân. Cả hai đều không dừng khi tìm thấy kết quả khớp, nên chi phí không phụ thuộc vào số bản sao của giá trị mục tiêu: khoảng 14 bước cho mỗi lần tìm kiếm với 10^4 giá trị.
Cận dưới trong tìm kiếm nhị phân là gì?
Cận dưới của một giá trị là chỉ số đầu tiên có phần tử lớn hơn hoặc bằng giá trị đó, hoặc là độ dài của danh sách nếu không có phần tử nào như vậy. Đó là vị trí cần chèn giá trị để giữ cho danh sách được sắp xếp. Cận trên là chỉ số đầu tiên có phần tử lớn hơn hẳn giá trị đó.
Liệu một hàm tìm kiếm nhị phân có thể tìm cả chỉ số đầu tiên và chỉ số cuối cùng không?
Đúng vậy. Thêm một cờ vào quá trình tìm kiếm: khi tìm thấy kết quả khớp, hãy ghi lại chỉ số rồi tiếp tục tìm sang trái để tìm bản sao đầu tiên, hoặc sang phải để tìm bản sao cuối cùng. Bạn cũng có thể gọi hàm tìm kiếm cận dưới trên target và target + 1. Cả hai đều chạy trong O(log n).
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def searchRange(nums, target):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Đối số
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Đầu ra mong đợi
[1, 3]