Second Largest Number

Q: Độ phức tạp thời gian khi tìm phần tử lớn thứ hai là bao nhiêu?

Cả phương pháp một lượt và hai lượt đều mất thời gian O(n) và dùng thêm O(1) bộ nhớ; sắp xếp trước sẽ mất O(n log n) . Bạn không thể làm tốt hơn O(n) , vì phải đọc mỗi giá trị một lần.

Người mớiMảng và chuỗi

+10

Bạn nhận được một danh sách số nguyên nums. Hãy trả về giá trị phân biệt lớn thứ hai: giá trị lớn nhất nhưng nhỏ hơn giá trị lớn nhất. Các giá trị có thể lặp lại, vì vậy với [5, 5, 3], đáp án là 3, không phải 5. Danh sách luôn có ít nhất hai giá trị khác nhau.

Hàm

secondLargest(nums: integer-array) → integer

numsinteger-array: danh sách số nguyên có ít nhất hai giá trị khác nhau
Trả vềinteger: giá trị lớn nhất nhỏ hơn giá trị tối đa

Ràng buộc

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums chứa ít nhất hai giá trị khác nhau.

Ví dụ

Đầu vào: nums = [4, 9, 2, 7, 9]
Đầu ra: 7
Giải thích: Giá trị lớn nhất là 9. Giá trị này xuất hiện hai lần, nhưng bản sao thứ hai không được tính, nên đáp án là giá trị nhỏ hơn tiếp theo, 7.

Đầu vào: nums = [-5, -1, -8]
Đầu ra: -5
Giải thích: Theo thứ tự từ lớn nhất đến nhỏ nhất, các giá trị là -1, -5, -8, vậy giá trị lớn thứ hai là -5.

Đầu vào: nums = [6, 6, 6, 3]
Đầu ra: 3
Giải thích: Chỉ có hai giá trị khác nhau là 6 và 3. Dù 6 lặp lại bao nhiêu lần, giá trị lớn thứ hai vẫn là 3.

Câu hỏi mở rộng

Bạn có thể trả về giá trị lớn thứ ba không trùng lặp chỉ trong một lượt duyệt, bằng ba biến (variable) và không sắp xếp 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

Giá trị lớn nhất có thể xuất hiện nhiều lần, và một giá trị lặp lại không được tính là giá trị lớn thứ hai. Đáp án có thể là số âm, vì vậy biến bắt đầu bằng 0 sẽ không xử lý đúng danh sách toàn số âm. Chỉ cần duyệt một lần và theo dõi hai giá trị phân biệt lớn nhất bằng các phép so sánh nghiêm ngặt là có thể xử lý cả hai trường hợp.

Sắp xếp rồi giảm dần vượt quá giá trị tối đa

Ý tưởng

Sắp xếp một bản sao rồi đi ngược từ cuối danh sách, bỏ qua từng giá trị lớn nhất cho đến khi gặp giá trị khác đầu tiên, đó là đáp án. Với [6, 6, 6, 3], bạn bỏ qua ba số 6 rồi dừng ở 3. Bạn không thể đi vượt quá đầu danh sách vì danh sách có hai giá trị khác nhau.

Sắp xếp sẽ xếp thứ tự tất cả giá trị trong khi bạn chỉ cần hai giá trị lớn nhất: thời gian O(n log n), cộng thêm bộ nhớ O(n) cho bản sao.

Thuật toán

Sao chép nums rồi sắp xếp bản sao theo thứ tự từ nhỏ đến lớn.
Bắt đầu chỉ số i ở vị trí cuối cùng.
Trong khi giá trị tại i bằng giá trị lớn nhất, hãy di chuyển i sang trái một bước.
Trả về giá trị tại i.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Hai lượt

Ý tưởng

Lần duyệt đầu tiên tìm giá trị lớn nhất. Lần duyệt thứ hai giữ lại giá trị lớn nhất nhỏ hơn nghiêm ngặt giá trị đó. Với [4, 9, 2, 7, 9], lần duyệt đầu tiên tìm thấy 9, còn lần thứ hai bỏ qua cả hai giá trị 9 và giữ lại 7.

Khởi tạo second với giá trị nhỏ hơn mọi giá trị hợp lệ. Có một giá trị nhỏ hơn giá trị lớn nhất, nên giá trị khởi tạo đó luôn được thay thế. Mỗi lần duyệt đều tìm giá trị lớn nhất hiện tại: độ phức tạp thời gian O(n) và độ phức tạp không gian O(1). Cái giá phải trả là đọc danh sách hai lần, và bạn không thể làm vậy với một luồng giá trị chỉ được xem một lần.

Thuật toán

Duyệt qua nums một lần và lưu giá trị lớn nhất vào largest.
Đặt second nhỏ hơn mọi giá trị hợp lệ.
Duyệt lại một lần nữa. Với mỗi x thỏa mãn x < largest và x > second, đặt second thành x.
Trả về second.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

Theo dõi hai giá trị lớn nhất trong một lượt duyệt

Ý tưởng

Giữ largest và second, hai giá trị phân biệt lớn nhất tính đến thời điểm hiện tại. Giá trị lớn hơn largest sẽ đẩy largest cũ xuống second. Giá trị nằm giữa second và largest sẽ thay thế second. Những giá trị khác, bao gồm một bản sao khác của largest, không làm thay đổi gì: các phép so sánh nghiêm ngặt bỏ qua giá trị trùng lặp.

Với [4, 9, 2, 7, 9], largest lần lượt nhận 4, rồi đến 9 với second = 4. 7 nằm giữa hai giá trị đó, nên second = 7, còn số 9 cuối cùng bị bỏ qua. Khởi tạo cả hai biến với giá trị nhỏ hơn mọi giá trị có thể có, vì đáp án có thể là số âm. Hai giá trị phân biệt bảo đảm second kết thúc với một giá trị trong danh sách.

Thuật toán

Đặt largest và second nhỏ hơn mọi giá trị được phép.
Lặp qua mọi giá trị x trong nums.
Nếu x > largest, chuyển largest vào second rồi đặt largest thành x.
Nếu không, nếu x < largest và x > second, đặt second thành x.
Sau vòng lặp, trả về second.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

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

Trả về phần tử áp chót của danh sách (list) đã sắp xếp. Nếu giá trị lớn nhất lặp lại, như trong [4, 9, 2, 7, 9], thì phần tử đó cũng là giá trị lớn nhất.
Khởi tạo các biến (variable) bằng 0. Với [-5, -1, -8], không có giá trị nào lớn hơn 0, nên bạn trả về 0, một giá trị không có trong danh sách.
Viết x >= largest trong trường hợp đầu tiên. Khi đó, số 9 thứ hai sẽ đẩy số 9 đầu tiên vào second, và bạn trả về 9.
Chỉ cập nhật second khi xuất hiện giá trị lớn nhất mới. Trong [10, 20, 15], số 15 không bao giờ được đưa vào second, nên bạn trả về 10.

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

Độ phức tạp thời gian khi tìm phần tử lớn thứ hai là bao nhiêu?

Cả phương pháp một lượt và hai lượt đều mất thời gian O(n) và dùng thêm O(1) bộ nhớ; sắp xếp trước sẽ mất O(n log n). Bạn không thể làm tốt hơn O(n), vì phải đọc mỗi giá trị một lần.

Các giá trị trùng lặp ảnh hưởng thế nào đến phần tử lớn thứ hai?

Bài toán này yêu cầu tìm giá trị phân biệt lớn thứ hai, vì vậy ta bỏ qua các bản sao của giá trị lớn nhất: [9, 9, 7] cho kết quả 7. Một số phiên bản tính theo vị trí và trả lời 9, vì vậy hãy kiểm tra xem đề bài muốn cách nào trước khi viết code.

Bạn nên trả về gì khi không có giá trị lớn thứ hai?

Ở đây, điều này không thể xảy ra vì danh sách chứa hai giá trị khác nhau. Nói chung, danh sách như [4, 4, 4] không có đáp án: hãy trả về một giá trị đánh dấu như -1 hoặc null, hoặc phát sinh lỗi. Bạn phát hiện trường hợp này khi second vẫn giữ giá trị ban đầu sau vòng lặp.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [4, 9, 2, 7, 9]

Đầu ra mong đợi

Second Largest Number

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Sắp xếp rồi giảm dần vượt quá giá trị tối đa

Hai lượt

Theo dõi hai giá trị lớn nhất trong một lượt duyệt

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

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

Bài tập tương tự