Tìm số lớn nhì và vị trí

An_Nguyen · September 20, 2019, 8:11am

Mọi người giú e thuật toán bài này với
Tìm phần tử có giá trị lớn thứ 2 trong mảng
INPUT: Dòng đầu tiên ghi số n.(2<=n<=30000)
Dòng tiếp theo ghi n số nguyên a[i] cách nhau bởi dấu cách.(1<=i<=n)(|a[i]|<=30000)
OUTPUT: Phần tử lớn thứ 2 của mảng và vị trí( nhỏ nhất nếu có nhiều kết quả)

KuroShiro · September 20, 2019, 8:34am

Tạo 1 mảng copy mảng đó, sắp xếp mảng copy => tìm được giá trị lớn thứ 2 trong mảng đã cho. Sau đó tìm vị trí của phần tử đầu tiên = giá trị lớn thứ 2 vừa tìm được trong mảng ban đầu.
Mình k chắc đây là cách tốt nhất.

Bui_Trung_Thong · September 20, 2019, 8:52am

trước phỏng vấn cũng từng bị hỏi câu như thế này, trả lời cũng như bác, tới giờ vẫn không rõ mình trả lời đúng hay sai, chỉ biết là rớt phỏng vấn

Sherly1001 · September 20, 2019, 9:20am

Duyệt qua mảng hai lần.

Lần một tìm max
Lần hai tìm max thứ hai (Như tìm max nhưng thêm điều kiện nhỏ hơn max)

Code python (code C/C++ bạn tự thử làm nha. )

a = [1, 2, 5, 2, 7, 4]

def max2(a):
    im = im2 = 0
    l = len(a)
    for i in range(l):
        if (a[im] < a[i]): im = i
    for i in range(l):
        if (a[im2] < a[i] and a[i] < a[im]): im2 = i
    return im2
im2 = max2(a)
print(im2, ':', a[im2])

Out:

2 : 5

tonghoangvu · September 20, 2019, 9:45am

Thì cứ từa tựa như tìm phần tử lớn nhất thôi.
Thay vì lưu giá trị thì mình lưu index, bài này dùng hai index i1 và i2 để lưu.
Mình code pascal, bạn viết lại bằng C++ nhé (đừng quên C++ đếm từ 0 trong khi pascal đếm từ 1)

i1 := 1;
i2 := 1;
for i := 2 to n do 
    if a[i] > a[i1] then
        begin
            i2 := i1;
            i1 := i;
        end;