Bài toán
Cho một dãy số nguyên dương gồm n phần tử (1≤n≤100000). Viết chương trình thực hiện các yêu cầu sau:
– Nhập n và các phần tử của dãy số.
– Tìm giá trị lớn thứ nhì của dãy số.
• Dữ liệu vào: được cho trong tệp văn bản có tên dayso.inp gồm
o Dòng đầu chứa số nguyên n.
o Dòng tiếp theo, chứa n số nguyên dương, các số cách nhau ít nhất một dấu cách.
• Kết quả ra: được ghi trong một tệp văn bản có tên dayso.out gồm một dòng chứa số lớn thứ nhì trong dãy. Nếu không tìm được số như vậy thì in ra duy nhất giá trị -1
Cài đặt bài toán
Để giải quyết bài toán này, bạn có thể sử dụng thuật toán sắp xếp để sắp xếp các phần tử trong dãy số theo thứ tự tăng dần, sau đó tìm giá trị lớn thứ hai của dãy số bằng cách lặp lại dãy số đã được sắp xếp và tìm phần tử đầu tiên mà khác với phần tử lớn nhất của dãy.
Dưới đây là code Python để giải quyết bài toán này:
# Đọc dữ liệu vào từ file dayso.inp
with open('dayso.inp', 'r') as f:
n = int(f.readline().strip())
arr = list(map(int, f.readline().strip().split()))
# Sắp xếp dãy số theo thứ tự tăng dần
arr.sort()
# Tìm giá trị lớn thứ hai trong dãy số
second_largest = -1
for i in range(n - 1, -1, -1):
if arr[i] < arr[-1]:
second_largest = arr[i]
break
# Ghi kết quả vào file dayso.out
with open('dayso.out', 'w') as f:
f.write(str(second_largest))
Trong đó, hàm open được sử dụng để mở file dayso.inp và dayso.out với các mode tương ứng là r (đọc) và w (ghi). Hàm readline được sử dụng để đọc từng dòng trong file. Hàm strip được sử dụng để loại bỏ ký tự xuống dòng (\n) và các khoảng trắng thừa ở đầu và cuối chuỗi. Hàm map được sử dụng để áp dụng hàm int lên từng phần tử của list được trả về bởi phương thức strip().split(). Cuối cùng, hàm write được sử dụng để ghi giá trị của biến second_largest vào file dayso.out.
Để cải thiện độ phức tạp của thuật toán, bạn có thể sử dụng phương pháp duyệt dãy số chỉ một lần và giữ lưu hai biến max1 và max2 để lưu giá trị lớn nhất và giá trị lớn thứ hai của dãy số. Trong quá trình duyệt, nếu phần tử tiếp theo lớn hơn max1, bạn cập nhật giá trị của max2 thành max1, và giá trị của max1 thành phần tử tiếp theo. Nếu phần tử tiếp theo nhỏ hơn hoặc bằng max1 nhưng lớn hơn max2, bạn chỉ cần cập nhật giá trị của max2 thành phần tử đó.
Dưới đây là code Python để giải quyết bài toán này với thuật toán tối ưu hơn:
# Đọc dữ liệu vào từ file dayso.inp
with open('dayso.inp', 'r') as f:
n = int(f.readline().strip())
arr = list(map(int, f.readline().strip().split()))
# Khởi tạo max1 và max2 là giá trị lớn nhất và giá trị lớn thứ hai
max1 = max2 = -1
# Duyệt dãy số và cập nhật giá trị của max1 và max2
for i in range(n):
if arr[i] > max1:
max2 = max1
max1 = arr[i]
elif arr[i] > max2:
max2 = arr[i]
# Ghi kết quả vào file dayso.out
with open('dayso.out', 'w') as f:
f.write(str(max2))
Trong đó, giá trị ban đầu của max1 và max2 là -1. Trong quá trình duyệt, nếu phần tử tiếp theo lớn hơn max1, bạn cập nhật giá trị của max2 thành max1, và giá trị của max1 thành phần tử tiếp theo. Nếu phần tử tiếp theo nhỏ hơn hoặc bằng max1 nhưng lớn hơn max2, bạn chỉ cần cập nhật giá trị của max2 thành phần tử đó. Sau khi duyệt xong, giá trị của max2 sẽ là giá trị lớn thứ hai của dãy số.