Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán cho ta 1 mảng gồm n phần tử được sắp xếp theo thứ tự tăng dần và chỉ chứa những phần tử có giá trị unique - không bị trùng, sau đó "xoay" mảng đó bằng việc đem phần tử cuối cùng lên vị trí đầu tiên của mảng từ 1 đến n lần. Hãy cùng xem qua ví dụ dưới đây với mảng nums = [0,1,2,4,5,6,7]:
- Sẽ trở thành [4,5,6,7,0,1,2] nếu nó được xoay 4 lần.
- Hay [0,1,2,4,5,6,7] tức là trở về như cũ, nếu nó được xoay tối đa n = 7 lần (n là số lượng phần tử trong mảng).
Và yêu cầu của bài toán là tìm phần tử nhỏ nhất với time-complexity là O(logn).
Chắc chắc ta sẽ không thể sort lại mảng input vì nó sẽ tốn ít nhất O(nlogn) time-complexity, chính vì vậy ta cần phải suy nghĩ xem liệu có thể áp dụng được Binary-Search để tìm cực tiểu - min value của mảng hay không.
Để áp dụng Binary-Search, mảng cần phải mang tính chất monotonic - đơn điệu trên khoảng nào đó. Với bài toán này, khi thực hiện phép xoay, ta sẽ thu được tối đa 2 khoảng tăng dần trong cùng 1 mảng, chính vì vậy ta có thể vô tư áp dụng Binary-Search trong bài toán này 😄
2. Solution & Phân Tích
Ta sẽ áp dụng Binary-Search để giải bài toán này, cụ thể là áp dụng template để tìm cực tiểu - mỗi lần thoả điều kiện ta sẽ để biến right giữ kết quả trả về (ngược lại là bài toán tìm cực đại - biến left sẽ đuợc dùng để lưu trữ kết quả).
Để áp dụng được, ta cần phải xác định các giá trị left, right, mid và đặc biệt là điều kiện để tăng left hoặc dùng right để lưu trữ kết quả. Về cơ bản, sẽ có 3 trường hợp xảy ra
- TH1: Left, Right và Mid cùng thẳng hàng - hay cùng nằm trên một khoảng đơn điệu
👉 nums[left] < nums[mid] < nums[right] - TH2: Left và Mid cùng nằm trên một khoảng đơn điệu. Right nằm trên khoảng đơn điệu khác
👉 nums[left] < nums[mid] > nums[right] - TH3: Right và Mid cùng nằm trên một khoảng đơn điệu. Left nằm trên khoảng đơn điệu khác
👉 nums[left] > nums[mid] < nums[right]
Ta nhận thấy, khi vị trí mid nằm bên trái giá trị min (trường hợp 2) hay: nums[mid] > nums[right] 🠆 cần tăng left = mid + 1 để loại bỏ khoảng giá trị dư thừa từ left đến mid trước đó.
Còn lại 2 trường hợp 1 và 3, giá trị mid đều nằm bên phải giá trị min (hoặc mid có thể nằm đúng vị trí của giá trị min) và nums[mid] luôn nhỏ hơn nums[right] 🠆 cần gán right = mid và dùng biến right như kết quả trả về, vì right sẽ ngày càng tiệm cận về giá trị min.
Một lưu ý nhỏ nữa là mảng nums chỉ bao gồm các phần tử unique, vì vậy chỉ có 2 trường hợp là nums[mid] > right hoặc nums[mid] < right chứ không có trường hợp bằng nhau.
Ta xét ví dụ sau:
- Input: nums = [4,5,6,7,0,1,2]
- Output: 0
Space-Complexity: O(1) - In-place algorithm
n: Số lượng phần tử trong mảng nums.
3. Code
Bài toán có áp dụng một cách làm khác khi chia đôi một số bằng việc dịch phải 1 bit, như vậy tổng quan hiện tại đang có 3 cách để chia đôi:
- (a + b) / 2
- (a + b) >> 2
- a + (b - a) / 2
Cách làm #3 vẫn là best practice và tránh tràn số trong trường hợp a và b có tổng quá lớn.
