LeetCode 0034

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

• Thẻ: Mảng, Tìm kiếm nhị phân
• Độ khó: Trung bình

Tóm tắt đề bài

Mô tả: Cho một mảng số nguyên $nums$ đã được sắp xếp theo thứ tự không giảm và một giá trị mục tiêu $target$.

Yêu cầu: Tìm vị trí bắt đầu và kết thúc của giá trị mục tiêu trong mảng.

Giải thích:

• Yêu cầu sử dụng thuật toán có độ phức tạp thời gian là $O(\log n)$.

Ví dụ:

• Ví dụ 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

• Ví dụ 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Ý tưởng

Ý tưởng 1: Tìm kiếm nhị phân

Thực hiện hai lần tìm kiếm nhị phân, lần đầu tiên tìm kiếm sang trái càng xa càng tốt. Lần thứ hai tìm kiếm sang phải càng xa càng tốt.

Ý tưởng 1: Code

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        n = len(nums)
        if n == 0:
            return ans
 
        left = 0
        right = n - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
 
        if nums[left] != target:
            return ans
 
        ans[0] = left
 
        left = 0
        right = n - 1
        while left < right:
            mid = left + (right - left + 1) // 2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid
 
        if nums[left] == target:
            ans[1] = left
 
        return ans

Ý tưởng 1: Độ phức tạp

• Độ phức tạp thời gian: $O(\log n)$.
• Độ phức tạp không gian: $O(1)$.

Ý tưởng 2: Sử dụng thư viện

Bản chất thì việc sử dụng thư viện cũng là tìm kiếm nhị phân nhưng chúng ta có thể viết code ngắn gọn hơn nhưng vẫn khuyến khích các bạn tự triển khai để hiểu hơn về tìm kiếm nhị phân. Trong Python, ta dùng bisect.bisect_left, trong C++ ta dùng hàm lower_bound và upper_bound. Các ngôn ngữ tôi không nắm rõ nên không trình bày.

Ý tưởng 2: Code

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = bisect_left(nums, target)
        r = bisect_left(nums, target + 1)
        return [-1, -1] if l == len(nums) or l >= r else [l, r - 1]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (l == nums.size() || nums[l] != target) 
            return {-1, -1};
        int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
        return {l, r};
    }
};

Ý tưởng 2: Độ phức tạp

• Độ phức tạp thời gian: $O(\log n)$.
• Độ phức tạp không gian: $O(1)$.