Mô tả vấn đề

Bài toán trình bày một mảng chứa một dãy số theo thứ tự tăng dần đã được quay từ 1 đến n lần. Xoay có nghĩa là các phần tử được dịch chuyển sang phải một vị trí và phần tử cuối cùng được chuyển sang vị trí đầu tiên. Nhiệm vụ là tìm phần tử nhỏ nhất trong mảng được xoay này. Thách thức là đạt được điều này bằng thuật toán chạy trong thời gian O(log n), điều này gợi ý rằng Tìm kiếm nhị phân nên sử dụng phương pháp này vì tìm kiếm nhị phân có độ phức tạp về thời gian logarit và thường được áp dụng cho các mảng được sắp xếp để nhanh chóng tìm thấy một phần tử cụ thể.

Tổng Quan

Chìa khóa để giải quyết vấn đề này nằm ở việc hiểu phép quay ảnh hưởng như thế nào đến mảng đã được sắp xếp. Mặc dù xoay, một phần của mảng vẫn được sắp xếp. Nếu mảng không được xoay hoặc đã được xoay toàn bộ chu kỳ (n lần) thì phần tử nhỏ nhất sẽ ở đầu. Nếu nó được xoay, mảng gồm hai dãy tăng dần và phần tử nhỏ nhất là phần tử đầu tiên của dãy thứ hai.

Vì vậy, chúng ta có thể sử dụng Tìm kiếm nhị phân để nhanh chóng xác định điểm xảy ra quá trình chuyển đổi từ giá trị cao hơn sang giá trị thấp hơn, điểm này cho biết phần tử nhỏ nhất. Tìm kiếm nhị phân được sửa đổi ở đây để so sánh phần tử ở giữa với phần tử đầu tiên và quyết định vị trí di chuyển tiếp theo:

1. Nếu phần tử ở giữa lớn hơn phần tử đầu tiên thì giá trị nhỏ nhất phải ở bên phải phần tử ở giữa. Do đó, chúng tôi tìm kiếm nửa bên phải của mảng.
2. Nếu phần tử ở giữa nhỏ hơn phần tử đầu tiên thì giá trị nhỏ nhất sẽ nằm ở đâu đó ở bên trái của phần tử ở giữa hoặc có thể chính là phần tử ở giữa. Ở đây, chúng tôi tìm kiếm nửa bên trái.

Bằng cách áp dụng logic này một cách đệ quy cho các nửa, điểm tồn tại của phần tử nhỏ nhất có thể được tìm thấy một cách hiệu quả, đáp ứng độ phức tạp về thời gian cần thiết..

Cách tiếp cận giải pháp

Việc thực hiện giải pháp thúc đẩy một Tìm kiếm nhị phân thuật toán tìm phần tử nhỏ nhất trong mảng đã quay. Dưới đây là các bước chi tiết của thuật toán:

1. Đầu tiên, giải pháp kiểm tra xem phần tử đầu tiên của mảng có nhỏ hơn hoặc bằng phần tử cuối cùng hay không. Nếu đúng, điều này cho biết mảng không được xoay hoặc được xoay toàn bộ chu kỳ. Do đó, phần tử đầu tiên đã là giá trị tối thiểu và chúng ta có thể trả về nó ngay lập tức.if nums[0] <= nums[-1]: return nums[0]
2. Nếu lần kiểm tra trước không thành công, giải pháp sẽ đặt hai con trỏ, left Và right, ở đầu và cuối mảng tương ứng. Những con trỏ này được sử dụng để thu hẹp vùng tìm kiếm một cách linh hoạt trong khi thực hiện Tìm kiếm nhị phân.left, right = 0, len(nums) - 1
3. Thuật toán đi vào một vòng lặp tiếp tục cho đến khi left con trỏ nhỏ hơn right con trỏ. Mục đích của vòng lặp này là liên tục thu hẹp không gian tìm kiếm cho đến khi xác định được phần tử tối thiểu..while left < right:
4. Bên trong vòng lặp, giải pháp tính toán mid điểm giữa con trỏ trái và phải. Điểm giữa này được sử dụng để so sánh các phần tử và quyết định nửa nào của mảng sẽ tìm kiếm tiếp theo.mid = (left + right) >> 1
5. Bước tiếp theo là so sánh phần tử tại mid chỉ mục với phần tử đầu tiên trong mảng. Nếu như nums[mid] lớn hơn nums[0], chúng ta biết rằng phần tử nhỏ nhất phải ở bên phải mid, vì vậy chúng tôi di chuyển left con trỏ tới mid + 1.if nums[0] <= nums[mid]: left = mid + 1
6. Ngược lại, nếu nums[mid] ít hơn nums[0], phần tử tối thiểu nằm ở bên trái của mid, hoặc nó có thể là mid chính nó, vì vậy chúng tôi di chuyển right con trỏ tới mid.else: right = mid
7. Vòng lặp tiếp tục cho đến khi left Và right con trỏ hội tụ về chỉ số của phần tử tối thiểu. Lúc này, chúng ta có thể quay lại nums[left] là phần tử tối thiểu của mảng.return nums[left]

Cách tiếp cận này đảm bảo rằng thời gian chạy sẽ là O(log n) vì nó liên tục loại bỏ một nửa không gian tìm kiếm trong mỗi lần lặp, đây là đặc điểm của phương pháp Tìm kiếm nhị phân.

Hướng dẫn ví dụ

Hãy xem xét một ví dụ nhỏ để minh họa cách tiếp cận giải pháp. Giả sử chúng ta có mảng xoay sau:

nums = [4, 5, 6, 7, 0, 1, 2]

Ban đầu, chúng tôi kiểm tra xem mảng chưa được xoay hay đã được xoay toàn bộ chu kỳ:

if nums[0] <= nums[-1]:
return nums[0]

Tuy nhiên, nums[0] là 4 Và nums[-1] là 2, vì vậy chúng tôi không trở lại nums[0] vì mảng đã được xoay.

Tiếp theo, chúng tôi thiết lập left Và right con trỏ:

left, right = 0, len(nums) - 1

Kể từ đây, left = 0 Và right = 6.

Bước vào vòng lặp, chúng ta tính toán mid chỉ số:

mid = (left + right) >> 1

Điều này giúp chúng tôi mid = 3, với nums[mid] = 7.

Bây giờ chúng ta so sánh nums[mid] với nums[0]. Từ 7 (phần tử ở giữa) lớn hơn 4 (phần tử đầu tiên), chúng tôi cập nhật left ĐẾN mid + 1:

left = mid + 1

Hiện nay, left = 4 Và right = 6.

Ở lần lặp tiếp theo, mid = (4 + 6) >> 1 = 5. giá trị nums[mid] là 1, đó là ít hơn nums[0].

Từ nums[mid] ít hơn nums[0], chúng tôi cập nhật right con trỏ tới mid:

right = mid

Hiện nay, left = 4 Và right = 5.

Tiếp tục vòng lặp, chúng ta tính toán tiếp theo mid:

mid = (left + right) >> 1 = (4 + 5) >> 1 = 4

Giá trị tại mid chỉ số là 0, đó là ít hơn nums[0]. Vì vậy, chúng tôi cập nhật right con trỏ tới mid lại:

right = mid

Kể từ bây giờ cả hai left Và right là 4, vòng lặp kết thúc và chúng tôi trả về giá trị nums[left] đó là 0, phần tử nhỏ nhất trong mảng được xoay:

return nums[left]

Do đó, theo cách tiếp cận được cung cấp, chúng tôi tìm thấy phần tử tối thiểu một cách hiệu quả trong một mảng được sắp xếp xoay trong thời gian O(log n).

C++

#include <vector> // Include the vector header for using the vector data structure
2
3class Solution {
4public:
5    // Function to find the minimum element in a rotated sorted array
6    int findMin(std::vector<int>& nums) {
7        int size = nums.size(); // Get the size of the vector
8      
9        // If the first element is less than or equal to the last element, 
10        // then the array is not rotated, so return the first element
11        if (nums[0] <= nums[size - 1]) {
12            return nums[0];
13        }
14      
15        int left = 0; // Initialize left pointer to the start of the array
16        int right = size - 1; // Initialize right pointer to the end of the array
17      
18        // Binary search to find the pivot, the smallest element
19        while (left < right) {
20            int mid = left + (right - left) / 2; // Find the mid index to prevent overflow
21          
22            // If the first element is less than or equal to the mid element,
23            // then the smallest value must be to the right of mid
24            if (nums[0] <= nums[mid]) {
25                left = mid + 1;
26            } else { // Otherwise, it is to the left of mid
27                right = mid;
28            }
29        }
30      
31        // At this point, left is the index of the smallest element
32        return nums[left];
33    }
34};

Độ phức tạp về thời gian và không gian

Mã Python được cung cấp triển khai thuật toán tìm kiếm nhị phân để tìm phần tử tối thiểu trong một mảng được sắp xếp xoay. Đây là phân tích về độ phức tạp về thời gian và không gian của nó:

Độ phức tạp thời gian:

Độ phức tạp về thời gian của thuật toán là O(log n), Ở đâu n là độ dài của danh sách đầu vào nums. Điều này là do thuật toán sử dụng phương pháp tìm kiếm nhị phân, trong đó nó liên tục chia khoảng thời gian tìm kiếm thành một nửa. Ở mỗi bước, thuật toán so sánh phần tử ở giữa với các phần tử biên để xác định nửa mảng cần tìm kiếm tiếp theo. Do đó, số bước cần thiết để tìm mức tối thiểu sẽ tỷ lệ thuận với logarit của kích thước mảng.

Độ phức tạp của không gian:

Độ phức tạp không gian của thuật toán là O(1), vì nó chỉ sử dụng một lượng không gian bổ sung không đổi. Các biến left, right, Và mid được sử dụng để duy trì giới hạn của không gian tìm kiếm và không có cấu trúc dữ liệu bổ sung nào được phân bổ phụ thuộc vào kích thước của danh sách đầu vào. Do đó, yêu cầu bộ nhớ không đổi bất kể kích thước đầu vào.