Bài toán Tìm vị trí đầu tiên và cuối cùng của phần tử trong mảng đã sắp xếp

Đề 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

1. 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.

2. 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.