Bài 34 Leetcode: Find First and Last Position of Element in Sorted Array

Đề bài:

Cho một mảng số nguyên `nums` đã được sắp xếp theo thứ tự không giảm, hãy tìm vị trí bắt đầu và kết thúc của giá trị `target` trong mảng. Nếu `target` không được tìm thấy trong mảng, trả về [-1, -1]. Bạn phải viết một thuật toán với độ phức tạp thời gian O(log n).

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]

Ví dụ 3:

Input: nums = [], target = 0
Output: [-1,-1]

Ràng buộc:

• 0 <= độ dài của nums <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums là một mảng không giảm.
• -10^9 <= target <= 10^9

Giải thích thuật toán bằng C++

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

Đoạn code trên là một đoạn code C++ để tìm vị trí bắt đầu và kết thúc của một giá trị `target` trong mảng `nums` đã được sắp xếp theo thứ tự không giảm. Dưới đây là giải thích về thuật toán trong đoạn code:

1. Sử dụng hàm `ranges::lower_bound` để tìm vị trí đầu tiên trong mảng `nums` mà giá trị tại đó không nhỏ hơn `target`. Trừ đi con trỏ đầu mảng `nums.begin()`, ta nhận được chỉ số `l` của vị trí bắt đầu.

2. Kiểm tra nếu `l` bằng với độ dài của mảng `nums` hoặc giá trị tại vị trí `l` không bằng `target`, tức là `target` không được tìm thấy trong mảng. Trong trường hợp này, ta trả về [-1, -1] để biểu thị rằng `target` không tồn tại trong mảng.

3. Sử dụng hàm `ranges::upper_bound` để tìm vị trí đầu tiên trong mảng `nums` mà giá trị tại đó lớn hơn `target`. Trừ đi con trỏ đầu mảng `nums.begin()` và trừ đi 1, ta nhận được chỉ số `r` của vị trí kết thúc.

4. Trả về một vector chứa giá trị `l` và `r`, biểu thị vị trí bắt đầu và kết thúc của `target` trong mảng `nums`.

Thuật toán trên sử dụng hai hàm `ranges::lower_bound` và `ranges::upper_bound` để tìm vị trí bắt đầu và kết thúc của `target` trong mảng `nums`. Độ phức tạp thời gian của thuật toán là O(log n), đảm bảo yêu cầu về độ phức tạp thời gian O(log n) theo yêu cầu của đề bài.

Giải thích thuật toán bằng Java

class Solution {
  public int[] searchRange(int[] nums, int target) {
    final int l = firstGreaterEqual(nums, target);
    if (l == nums.length || nums[l] != target)
      return new int[] {-1, -1};
    final int r = firstGreaterEqual(nums, target + 1) - 1;
    return new int[] {l, r};
  }

  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

Giải thích thuật toán bằng Python

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