Đề bài:
Cho một mảng số nguyên `nums` đã được sắp xếp theo thứ tự tăng dần (với các giá trị riêng biệt).
Trước khi được truyền vào hàm của bạn, `nums` có thể đã được xoay vòng ở một vị trí không biết `k` (1 <= k < độ dài của nums) sao cho mảng kết quả là [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (đánh số từ 0). Ví dụ, [0,1,2,4,5,6,7] có thể đã được xoay vòng ở vị trí `k = 3` và trở thành [4,5,6,7,0,1,2].
Cho mảng `nums` sau khi xoay vòng và một số nguyên `target`, hãy trả về chỉ số của `target` trong `nums` nếu nó có trong mảng, hoặc trả về -1 nếu nó không có trong `nums`.
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 = [4,5,6,7,0,1,2], target = 0 Output: 4
Ví dụ 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Ví dụ 3:
Input: nums = [1], target = 0 Output: -1
Ràng buộc:
- 1 <= độ dài của nums <= 5000
- -10^4 <= nums[i] <= 10^4
- Tất cả các giá trị trong nums đều là duy nhất.
- nums là một mảng tăng dần có thể đã được xoay vòng.
- -10^4 <= target <= 10^4
Giải thích thuật toán bằng C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
const int m = (l + r) / 2;
if (nums[m] == target)
return m;
if (nums[l] <= nums[m]) { // nums[l..m] are sorted
if (nums[l] <= target && target < nums[m])
r = m - 1;
else
l = m + 1;
} else { // nums[m..n - 1] are sorted
if (nums[m] < target && target <= nums[r])
l = m + 1;
else
r = m - 1;
}
}
return -1;
}
};
Đoạn code trên là một đoạn code C++ để tìm chỉ số của một số nguyên `target` trong mảng `nums` đã được sắp xếp và có thể đã được xoay vòng. Dưới đây là giải thích về thuật toán trong đoạn code:
1. Khai báo hai biến `l` và `r`, lần lượt là chỉ số bắt đầu và kết thúc của mảng `nums`.
2. Sử dụng vòng lặp while để thực hiện tìm kiếm trong mảng:
– Tính chỉ số giữa `m` bằng cách lấy trung bình của `l` và `r`: `m = (l + r) / 2`.
– Nếu giá trị `nums[m]` bằng `target`, tức là đã tìm thấy `target`, ta trả về chỉ số `m`.
– Nếu mảng con từ `nums[l]` đến `nums[m]` được sắp xếp (không bị xoay vòng), ta kiểm tra xem `target` có nằm trong khoảng giữa `nums[l]` và `nums[m]` hay không. Nếu có, ta cập nhật `r = m – 1` để thu hẹp phạm vi tìm kiếm trong mảng con này. Nếu không, ta cập nhật `l = m + 1` để bỏ qua mảng con này trong tìm kiếm.
– Ngược lại, nếu mảng con từ `nums[m]` đến `nums[r]` được sắp xếp (không bị xoay vòng), ta kiểm tra xem `target` có nằm trong khoảng giữa `nums[m]` và `nums[r]` hay không. Nếu có, ta cập nhật `l = m + 1` để bỏ qua mảng con này trong tìm kiếm. Nếu không, ta cập nhật `r = m – 1` để thu hẹp phạm vi tìm kiếm trong mảng con này.
3. Nếu không tìm thấy `target` trong mảng `nums`, ta trả về -1.
Thuật toán trên sử dụng phương pháp tìm kiếm nhị phân để tìm chỉ số của `target` trong mảng `nums`. Bằng cách sử dụng các điều kiện kiểm tra và thu hẹp phạm vi tìm kiếm, thuật toán đảm bảo độ phức tạp thời gian O(log n).
Giải thích thuật toán bằng Java
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
final int m = (l + r) / 2;
if (nums[m] == target)
return m;
if (nums[l] <= nums[m]) { // nums[l..m] are sorted.
if (nums[l] <= target && target < nums[m])
r = m - 1;
else
l = m + 1;
} else { // nums[m..n - 1] are sorted.
if (nums[m] < target && target <= nums[r])
l = m + 1;
else
r = m - 1;
}
}
return -1;
}
}
Giải thích thuật toán bằng Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
if nums[l] <= nums[m]: # nums[l..m] are sorted.
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else: # nums[m..n - 1] are sorted.
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return -1
0 / 5 - (0 Đánh Giá)