Pattern · Tìm kiếm nhị phânTrung bình
Tìm Giá Trị Nhỏ Nhất Trong Mảng XoayFind Minimum in Rotated Sorted Array
Hiểu bài
Cho mảng số nguyên phân biệt nums đã được sắp xếp tăng dần, sau đó xoay tại một vị trí bí mật. Tìm phần tử nhỏ nhất trong mảng.
Ví dụ:
ts
nums = [3, 4, 5, 1, 2]
output = 1 // mảng gốc [1,2,3,4,5] xoay 3 bước
nums = [4, 5, 6, 7, 0, 1, 2]
output = 0 // mảng gốc [0,1,2,4,5,6,7] xoay 4 bước
nums = [11, 13, 15, 17]
output = 11 // không xoay (hoặc xoay đủ vòng)Thuật toán phải chạy trong O(log n) — không được dùng vòng lặp tuyến tính.
Cách cơ bản
O(n) time, O(1) spacets
function findMin(nums: number[]): number {
return Math.min(...nums) // hoặc dùng vòng lặp tuyến tính
}Vì sao cách này chậm:
Duyệt toàn bộ mảng để tìm min vi phạm ràng buộc O(log n) của đề.
Cần tận dụng việc dù mảng bị xoay, luôn có một nửa còn giữ nguyên thứ tự sắp xếp để cắt nửa mỗi bước.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.