Find the Largest Number

Q: Độ phức tạp thời gian khi tìm giá trị lớn nhất trong một mảng là bao nhiêu?

Một lượt duyệt mất thời gian O(n) và tốn thêm O(1) không gian. Không có phương pháp nào trên mảng chưa được sắp xếp hiệu quả hơn, vì bất kỳ phần tử nào bạn không đọc đều có thể là phần tử lớn nhất. Sắp xếp trước tốn O(n log n) .

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

+10

Bạn có một danh sách số nguyên không rỗng nums. Hãy trả về giá trị lớn nhất trong danh sách. Các giá trị có thể là số âm, nên đáp án cũng có thể là số âm. Hãy tìm giá trị đó bằng cách tự so sánh, không dùng hàm tìm giá trị lớn nhất có sẵn như max.

Hàm

findMax(nums: integer-array) → integer

numsinteger-array: danh sách số nguyên cần tìm kiếm
Trả vềinteger: giá trị lớn nhất trong nums

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Ví dụ

Đầu vào: nums = [3, 17, 4, 12, 9]
Đầu ra: 17
Giải thích: Đọc từ trái sang phải, giá trị lớn nhất tính đến lúc này là 3, rồi đến 17. Không có giá trị nào trong 4, 12 hoặc 9 lớn hơn 17.

Đầu vào: nums = [-8, -3, -11, -3]
Đầu ra: -3
Giải thích: Mọi giá trị đều âm và -3 gần 0 nhất, nên đó là giá trị lớn nhất. Giá trị này xuất hiện hai lần, nhưng bạn trả về giá trị chứ không phải vị trí.

Câu hỏi mở rộng

Bạn có thể tìm cả giá trị lớn nhất và nhỏ nhất chỉ với khoảng 3n/2 phép so sánh thay vì 2n phép so sánh bằng cách so sánh các giá trị theo từng cặp trước 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ị nào bạn bỏ qua cũng có thể là giá trị lớn nhất, vì vậy mọi lời giải đều đọc từng phần tử. Chỉ cần duyệt một lượt và cập nhật giá trị lớn nhất, không cần làm gì thêm. Khởi tạo giá trị lớn nhất bằng phần tử đầu tiên, không phải 0, vì mọi giá trị đều có thể âm.

Sắp xếp bản sao và lấy giá trị cuối cùng

Ý tưởng

Sao chép nums để danh sách của bên gọi không thay đổi, sắp xếp bản sao từ nhỏ đến lớn rồi trả về phần tử cuối cùng. Với [3, 17, 4, 12, 9], bản sao đã sắp xếp là [3, 4, 9, 12, 17].

Sắp xếp đưa mọi giá trị vào đúng thứ tự khi bạn chỉ cần giá trị lớn nhất. Cách này cần khoảng n log n phép so sánh, xấp xỉ 60,000 với n = 5000, cùng với bộ nhớ O(n) cho bản sao.

Thuật toán

Sao chép nums.
Sắp xếp bản sao theo thứ tự từ nhỏ nhất đến lớn nhất, so sánh các số dưới dạng số.
Trả về phần tử cuối cùng của bản sao đã sắp xếp.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Một lượt duyệt với giá trị lớn nhất hiện tại

Ý tưởng

Giữ largest, giá trị lớn nhất đã gặp cho đến nay, và thay thế nó mỗi khi có giá trị lớn hơn. Sau vòng lặp, giá trị này đã được so sánh với mọi phần tử, nên không có giá trị nào trong danh sách lớn hơn nó. Với [3, 17, 4, 12, 9], giá trị bắt đầu là 3, đổi thành 17 rồi giữ nguyên: n-1 lần so sánh và thêm một biến.

Bắt đầu từ nums[0] giúp xử lý được các danh sách có số âm. Nếu bắt đầu từ 0, không có giá trị nào trong [-8, -3, -11, -3] lớn hơn nó, nên bạn trả về 0, một giá trị không có trong danh sách.

Thuật toán

Đặt largest thành nums[0].
Lặp qua mọi giá trị x trong nums.
Nếu x > largest, đặt largest thành x.
Sau vòng lặp, trả về largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

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

Bắt đầu với một số nhỏ được đoán, chẳng hạn như -1000000. Các giá trị có thể xuống đến -10^9, vì vậy [-2000000] sẽ trả về số bạn đã đoán. nums[0] không cần đoán.
Đọc nums[0] trong Lua hoặc R, nơi phần tử đầu tiên là nums[1]. Lua trả về nil, còn R trả về một vector rỗng.
Lặp với i ≤ n trên các chỉ số bắt đầu từ 0, khiến chương trình đọc vượt quá phần tử cuối cùng một vị trí.
Sắp xếp mà không có hàm so sánh số trong JavaScript hoặc TypeScript. Thứ tự văn bản của [3, 17, 4, 12, 9] kết thúc bằng 9, vì vậy bạn trả về 9.

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

Độ phức tạp thời gian khi tìm giá trị lớn nhất trong một mảng là bao nhiêu?

Một lượt duyệt mất thời gian O(n) và tốn thêm O(1) không gian. Không có phương pháp nào trên mảng chưa được sắp xếp hiệu quả hơn, vì bất kỳ phần tử nào bạn không đọc đều có thể là phần tử lớn nhất. Sắp xếp trước tốn O(n log n).

Làm thế nào để tìm số lớn nhất trong mảng mà không dùng max?

Lưu phần tử đầu tiên vào một biến. Lặp qua các phần tử còn lại và lưu phần tử đó thay thế mỗi khi gặp một phần tử lớn hơn. Khi vòng lặp kết thúc, biến chứa giá trị lớn nhất.

Khi nào sắp xếp là một cách hay để tìm giá trị lớn nhất?

Khi bạn cần tìm nhiều hơn giá trị lớn nhất, chẳng hạn như ba giá trị lớn nhất hoặc giá trị trung vị, và sẽ đặt nhiều câu hỏi tương tự về cùng một danh sách. Nếu chỉ cần tìm giá trị lớn nhất, duyệt qua danh sách một lần sẽ nhanh hơn và không làm thay đổi danh sách.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 17, 4, 12, 9]

Đầu ra mong đợi