Đề bài
Cho một mảng số nguyên nums được sắp xếp theo thứ tự tăng dần và một số nguyên target, hãy tìm vị trí bắt đầu và kết thúc của target trong mảng.
Nếu target không có trong mảng, trả về [-1, -1].
Ví dụ:
Đầu vào: nums = [5,7,7,8,8,10], target = 8
Đầu ra: [3,4]
Đầu vào: nums = [5,7,7,8,8,10], target = 6
Đầu ra: [-1,-1]
Đầu vào: nums = [], target = 0
Đầu ra: [-1,-1]
Ràng buộc:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Mảng nums được sắp xếp tăng dần.
-10^9 <= target <= 10^9
Ý tưởng giải
Sử dụng tìm kiếm nhị phân (binary search) để tìm vị trí đầu tiên và cuối cùng của target. Vì mảng đã được sắp xếp, ta có thể:
Tìm vị trí đầu tiên của target bằng cách sử dụng tìm kiếm nhị phân để tìm phần tử đầu tiên bằng hoặc lớn hơn target.
Tìm vị trí cuối cùng của target bằng cách sử dụng tìm kiếm nhị phân để tìm phần tử cuối cùng bằng hoặc nhỏ hơn target.
Nếu cả hai vị trí đều hợp lệ và giá trị tại các vị trí đó là target, trả về [first, last]. Ngược lại, trả về [-1, -1].
Thời gian phức tạp: O(log n), vì tìm kiếm nhị phân có độ phức tạp O(log n) và ta thực hiện nó hai lần.
def searchRange(nums, target): def binarySearch(nums, target, findFirst): left, right = 0, len(nums) - 1 result = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: result = mid if findFirst: right = mid - 1 # Tiếp tục tìm bên trái để tìm vị trí đầu tiên else: left = mid + 1 # Tiếp tục tìm bên phải để tìm vị trí cuối cùng elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return result # Tìm vị trí đầu tiên và cuối cùng first = binarySearch(nums, target, True) last = binarySearch(nums, target, False) return [first, last] Giải thích code
- Hàm binarySearch:
Tham số findFirst quyết định xem ta đang tìm vị trí đầu tiên (True) hay cuối cùng (False).
Nếu tìm thấy target tại mid, lưu lại result nhưng tiếp tục tìm:
Nếu findFirst = True, tiếp tục tìm ở nửa bên trái để tìm vị trí đầu tiên.
Nếu findFirst = False, tiếp tục tìm ở nửa bên phải để tìm vị trí cuối cùng.
Nếu nums[mid] != target, thực hiện tìm kiếm nhị phân thông thường.
- Hàm chính searchRange:
Gọi binarySearch hai lần:
Lần đầu với findFirst = True để tìm vị trí đầu tiên.
Lần hai với findFirst = False để tìm vị trí cuối cùng.
Trả về mảng [first, last].
Độ phức tạp
Thời gian: O(log n), do mỗi lần tìm kiếm nhị phân có độ phức tạp O(log n) và ta thực hiện hai lần.
Không gian: O(1), chỉ sử dụng một số biến phụ.
Kết luận
Giải pháp sử dụng tìm kiếm nhị phân là tối ưu cho bài toán này vì tận dụng được tính chất mảng đã sắp xếp, đảm bảo hiệu quả về thời gian. Code trên có thể xử lý tất cả các trường hợp, bao gồm mảng rỗng và target không tồn tại.