Với mảng cho trước bao gồm n phần tử là số nguyên, tìm phần tử lớn thứ hai trong mảng (Find second largest number in an array). Đây là một trong những câu hỏi phỏng vấn mà tôi đã từng gặp. Tìm số lớn nhất trong mảng thì hẳn ai cũng biết, nhưng số lớn thứ hai thì có thể sẽ làm kha khá bạn lúng túng.
Giải thuật với tên gọi "Find second largest number in an array" được mô tả như sau:
1) Initialize two variables first and second to INT_MIN as,
first = second = INT_MIN
2) Start traversing the array,
a) If the current element in array say arr[i] is greater
than first. Then update first and second as,
second = first
first = arr[i]
b) If the current element is in between first and second,
then update second to store the value of current variable as
second = arr[i]
3) Return the value stored in second.
Ứng với mô tả trên, cài đặt bằng C của thuật toán sẽ tương tự như sau:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
int main() {
int n = 10;
int *a = (int*) calloc(n, sizeof(int));
srand(time(0));
for (int i = 0; i < n; i++) {
a[i] = rand() % 201;
printf("%d ", a[i]);
}
int max, second_max;
max = second_max = INT_MIN;
for (int i = 0; i < n; i++) {
if (a[i] > max) {
second_max = max;
max = a[i];
} else if (a[i] > second_max && a[i] < max) {
second_max = a[i];
}
}
printf("\nmax=%d, second_max=%d", max, second_max);
return 0;
}Bonus: Cài đặt bằng Python của thuật toán:
import sys
if __name__ == '__main__':
n = int(input())
arr = map(int, input().split())
a = list(arr)
max = -sys.maxsize - 1
second_max = max
for i in a:
if i > max:
second_max = max
max = i
elif i < max and i > second_max:
second_max = i
print(second_max)
Chú thích:
- Tạo mảng động với n = 10 phần từ.
- Giá trị của mỗi phần tử được sinh ngẫu nhiên trong khoảng từ 0 đến 200.
- In ra phần tử lớn nhất và phần tử lớn thứ nhì, kết thúc chương trình.
Kết quả sau khi chạy chương trình (Output):
151 99 178 126 31 36 70 129 117 159
max=178, second_max=159
Loading...