Tìm số lớn thứ hai của mảng (VT02)

Nguồn: CLUE OJ Độ khó: Trung bình Mảng 1 chiều Mã bài VT02

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử. Hãy tìm phần tử lớn thứ hai của mảng.

Phần tử lớn thứ hai phải nhỏ hơn hẳn phần tử lớn nhất (không chấp nhận giá trị bằng phần tử lớn nhất). Nói cách khác, đó là giá trị lớn nhất trong số các phần tử nhỏ hơn số lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên dương $n$ – số phần tử của mảng.
• Dòng thứ hai gồm $n$ số nguyên $A_1, A_2, \ldots, A_n$, cách nhau bởi dấu cách.

Kết quả:

• Nếu tìm được phần tử lớn thứ hai, in ra giá trị đó.
• Nếu không có (mọi phần tử đều bằng nhau), in ra NOT FOUND.

Giới hạn:

• $2 \le n \le 10^6$
• $|A_i| \le 10^9$

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3
1 2 3

Ví dụ 1 – output

2

Giải thích:

• Số lớn nhất là $3$, số lớn thứ hai là $2$.
• Với mảng $7, 7, 7, 3, 7$ thì đáp án là $3$ (không phải $7$). Với mảng $5, 5$ thì in NOT FOUND.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Ý tưởng

Thầy giữ hai biến: max1 là số lớn nhất, max2 là số lớn thứ hai (nhỏ hơn hẳn max1), ban đầu đều là "chưa có" (trong C++ dùng LLONG_MIN, nhỏ hơn mọi phần tử vì $|A_i| \le 10^9$). Duyệt từng phần tử $x$:

• Nếu $x > max1$: số lớn nhất cũ lùi xuống hạng hai (max2 = max1), rồi max1 = x.
• Ngược lại, nếu $x < max1$ và $x > max2$ thì max2 = x. (Nếu $x = max1$ thì bỏ qua.)

Cuối cùng max2 vẫn là "chưa có" thì in NOT FOUND.

Chạy tay với $1, 2, 3$: $x=1$ → max1 = 1; $x=2$ → max2 = 1, max1 = 2; $x=3$ → max2 = 2, max1 = 3. Đáp án $2$.

Lưu ý / bẫy thường gặp

• Lấy phần tử lớn nhất ở vị trí khác (hoặc sắp xếp rồi lấy A[n-2]) sẽ ra số bằng số lớn nhất khi có trùng – sai yêu cầu "nhỏ hơn hẳn".
• Khởi tạo max1 = max2 = 0: mảng toàn số âm sẽ sai.
• Dùng -10^9 làm giá trị "chưa có": nếu đáp án đúng bằng $-10^9$ thì em lại in NOT FOUND. Hãy dùng giá trị nằm ngoài phạm vi (LLONG_MIN) hoặc biến cờ.
• Quên trường hợp mọi phần tử bằng nhau (phải in NOT FOUND).
• Khi gặp số lớn nhất mới mà quên max2 = max1 thì mất số lớn thứ hai.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇