Find Minimum in Rotated Sorted Array

Q: Độ phức tạp thời gian khi tìm giá trị nhỏ nhất trong một mảng đã sắp xếp rồi xoay là bao nhiêu?

Thời gian O(log n) và bộ nhớ bổ sung O(1) khi dùng tìm kiếm nhị phân, tối đa 13 phép so sánh cho 5000 phần tử. Quá trình đi tìm điểm giảm mất O(n) : nó đọc mọi phần tử khi giá trị nhỏ nhất nằm ở cuối.

Q: Vì sao so sánh nums[mid] với nums[hi] chứ không phải với nums[lo]?

nums[hi] luôn xác định phía nào có giá trị nhỏ nhất. Với nums[lo] , kết quả nums[mid] > nums[lo] phù hợp với cả một khoảng chưa xoay, trong đó giá trị nhỏ nhất là nums[lo] , và một khoảng đã xoay, trong đó giá trị nhỏ nhất nằm bên phải mid .

Q: Bạn tìm số lần một mảng đã sắp xếp bị xoay như thế nào?

Chạy cùng một thuật toán tìm kiếm nhị phân và lấy lo , chỉ số của phần tử nhỏ nhất. Nếu phép xoay chuyển phần tử cuối cùng lên đầu, chỉ số đó là số lần xoay. Nếu phép xoay chuyển phần tử đầu tiên xuống cuối như ở đây, số lần xoay là (n - lo) mod n : 7 trừ 4 bằng 3 trong ví dụ đầu tiên.

Q: Tìm kiếm nhị phân có hoạt động khi mảng có các phần tử trùng lặp không?

Không còn giữ nguyên. Trong [2, 2, 2, 0, 2] , nums[mid] có thể bằng nums[hi] , nên không thể loại bỏ bên nào. Khi đó, đặt hi = hi - 1 là an toàn vì vẫn còn một bản sao của nums[hi] trong phạm vi, nhưng trường hợp xấu nhất có độ phức tạp là O(n) .

Trung bìnhTìm kiếm nhị phân

+10

Một danh sách các số nguyên khác nhau được sắp xếp theo thứ tự tăng dần rồi xoay: một số phần tử, có thể bằng 0, được lấy từ đầu danh sách và chuyển ra cuối theo cùng thứ tự. Ví dụ, xoay [2, 5, 9, 11, 13, 15, 17] đi 3 vị trí sẽ thành [11, 13, 15, 17, 2, 5, 9]. Bạn được cung cấp danh sách đã xoay nums. Hãy trả về giá trị nhỏ nhất trong thời gian O(log n).

Hàm

findMin(nums: integer-array) → integer

numsinteger-array: danh sách các số nguyên phân biệt đã được xoay
Trả vềinteger: giá trị nhỏ nhất trong nums

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Tất cả giá trị trong nums đều khác nhau.
nums là một danh sách tăng dần được xoay đi k vị trí, với 0 ≤ k < nums.length; k = 0 nghĩa là danh sách không bị xoay.

Ví dụ

Đầu vào: nums = [11, 13, 15, 17, 2, 5, 9]
Đầu ra: 2
Giải thích: Các giá trị tăng lên 17 rồi giảm xuống 2. Vì 17 > 9, giá trị nhỏ nhất nằm bên phải chỉ số 3; sau đó, 5 ≤ 9 và 2 ≤ 5 đưa hi trở lại chỉ số 4, nơi có giá trị 2.

Đầu vào: nums = [4, 7, 10, 12]
Đầu ra: 4
Giải thích: Danh sách này đã được xoay 0 lần, nên vẫn được sắp xếp và giá trị nhỏ nhất là giá trị đầu tiên. Mọi giá trị ở giữa đều nhỏ hơn hoặc bằng giá trị cuối cùng, vì vậy hi tiếp tục di chuyển sang trái cho đến khi đạt chỉ số 0, nơi có giá trị 4.

Đầu vào: nums = [30, -6, 0, 8, 19]
Đầu ra: -6
Giải thích: Xoay 4 vị trí sẽ đưa giá trị lớn nhất, 30, lên đầu tiên và giá trị nhỏ nhất, -6, đến chỉ số 1. Phạm vi tìm kiếm thu hẹp còn chỉ số 0 và 1, thấy 30 > -6, rồi chuyển lo thành 1.

Câu hỏi mở rộng

Bạn có thể trả về giá trị nhỏ thứ k của nums trong thời gian O(log n) mà không sắp xếp mảng không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một danh sách đã sắp xếp và bị xoay gồm hai đoạn tăng dần, và giá trị nhỏ nhất bắt đầu đoạn thứ hai, ngay sau vị trí duy nhất mà các giá trị giảm xuống. So sánh giá trị ở giữa với giá trị cuối cùng trong phạm vi sẽ cho bạn biết giá trị ở giữa nằm về phía nào của chỗ giảm đó, vì vậy tìm kiếm nhị phân (binary search) sẽ tìm ra giá trị nhỏ nhất trong O(log n).

Đi bộ cho đến khi các giá trị giảm

Ý tưởng

Phép xoay giữ cho cả hai đoạn đều được sắp xếp và tạo ra một vị trí mà tại đó một giá trị nhỏ hơn giá trị đứng trước nó: giá trị lớn nhất đứng ngay trước giá trị nhỏ nhất. Duyệt từ trái sang phải và trả về giá trị đầu tiên như vậy. Nếu không có giá trị nào, danh sách chưa bị xoay và giá trị nhỏ nhất là nums[0].

Điểm giảm có thể nằm ở bất cứ đâu. Khi phép xoay dịch chuyển một phần tử, như trong [2, 3, 4, 5, 6, 7, 8, 1], lượt duyệt sẽ đọc toàn bộ danh sách: 5000 phép so sánh cho 5000 phần tử, trong khi tìm kiếm nhị phân chỉ cần 13 phép so sánh.

Thuật toán

Với mỗi chỉ số i từ 1 đến n-1, hãy so sánh nums[i] với nums[i-1].
Nếu nums[i] < nums[i-1], hãy trả về nums[i]: đoạn thứ hai bắt đầu tại đó.
Nếu vòng lặp kết thúc, danh sách chưa được xoay: hãy trả về nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Tìm kiếm nhị phân với giá trị cuối cùng

Ý tưởng

Hãy giữ một cam kết: giá trị nhỏ nhất nằm trong khoảng từ lo đến hi, bao gồm cả hai đầu. So sánh giá trị ở giữa với nums[hi], giá trị cuối cùng trong phạm vi.

Nếu nums[mid] > nums[hi], các giá trị giảm ở đâu đó trong khoảng từ mid đến hi, và giá trị nhỏ nhất nằm ngay sau chỗ giảm đó, nên đặt lo = mid + 1. Nếu không, nums[mid] < nums[hi], vì các giá trị khác nhau, nên nums[mid..hi] tăng dần mà không có chỗ giảm nào. Giá trị nhỏ nhất là nums[mid] hoặc nằm trước nó: đặt hi = mid, giữ mid trong phạm vi. Cả hai cách cập nhật đều giữ nguyên cam kết và thu hẹp phạm vi, nên khi lo gặp hi, giá trị duy nhất còn lại chính là giá trị nhỏ nhất.

Mỗi bước giảm một nửa phạm vi: tối đa 13 bước với 5000 phần tử, dùng thêm hai chỉ số bộ nhớ.

Thuật toán

Đặt lo = 0 và hi = n-1.
Khi lo < hi, tính mid = lo + (hi - lo) / 2.
Nếu nums[mid] > nums[hi], đặt lo = mid + 1.
Nếu không, đặt hi = mid.
Khi vòng lặp kết thúc, trả về nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Lỗi thường gặp và trường hợp biên

Viết hi = mid - 1 trong nhánh thứ hai. Trong [3, 1, 2], giá trị ở giữa là 1, không lớn hơn 2, nên hi giảm xuống 0 và hàm trả về 3.
Lặp với điều kiện lo ≤ hi. Khi lo bằng hi, hi = mid không làm thay đổi gì và vòng lặp không bao giờ kết thúc.
So sánh với nums[lo] thay vì nums[hi]. Trong danh sách chưa xoay [1, 2, 3, 4, 5], giá trị ở giữa là 3, lớn hơn nums[0] = 1, nên lượt tìm kiếm đi sang phải và trả về 4.
Không dự phòng trường hợp danh sách chưa xoay khi duyệt. Trong [4, 7, 10, 12], không có phần tử nào giảm xuống, nên trả về nums[0].

Câu hỏi thường gặp4

Độ phức tạp thời gian khi tìm giá trị nhỏ nhất trong một mảng đã sắp xếp rồi xoay là bao nhiêu?

Thời gian O(log n) và bộ nhớ bổ sung O(1) khi dùng tìm kiếm nhị phân, tối đa 13 phép so sánh cho 5000 phần tử. Quá trình đi tìm điểm giảm mất O(n): nó đọc mọi phần tử khi giá trị nhỏ nhất nằm ở cuối.

Vì sao so sánh nums[mid] với nums[hi] chứ không phải với nums[lo]?

nums[hi] luôn xác định phía nào có giá trị nhỏ nhất. Với nums[lo], kết quả nums[mid] > nums[lo] phù hợp với cả một khoảng chưa xoay, trong đó giá trị nhỏ nhất là nums[lo], và một khoảng đã xoay, trong đó giá trị nhỏ nhất nằm bên phải mid.

Bạn tìm số lần một mảng đã sắp xếp bị xoay như thế nào?

Chạy cùng một thuật toán tìm kiếm nhị phân và lấy lo, chỉ số của phần tử nhỏ nhất. Nếu phép xoay chuyển phần tử cuối cùng lên đầu, chỉ số đó là số lần xoay. Nếu phép xoay chuyển phần tử đầu tiên xuống cuối như ở đây, số lần xoay là (n - lo) mod n: 7 trừ 4 bằng 3 trong ví dụ đầu tiên.

Tìm kiếm nhị phân có hoạt động khi mảng có các phần tử trùng lặp không?

Không còn giữ nguyên. Trong [2, 2, 2, 0, 2], nums[mid] có thể bằng nums[hi], nên không thể loại bỏ bên nào. Khi đó, đặt hi = hi - 1 là an toàn vì vẫn còn một bản sao của nums[hi] trong phạm vi, nhưng trường hợp xấu nhất có độ phức tạp là O(n).

def findMin(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [11, 13, 15, 17, 2, 5, 9]

Đầu ra mong đợi