Thuật toán mảng: tìm max, đếm, tìm kiếm, trung bình
Công việc mảng phổ biến
- Một số bài tập mảng xuất hiện lặp đi lặp lại: tìm tổng, lớn nhất, nhỏ nhất, hoặc đếm các mục.
- Mỗi cái đều sử dụng cùng một ý tưởng: bắt đầu với một giả định, sau đó lặp và cập nhật nó.
- Các mẫu này xuất hiện liên tục trong kỳ thi AP CSA.
Tổng và đếm
- Giữ một tổng tích lũy bắt đầu từ 0, và cộng từng giá trị.
- Để đếm các mục vượt qua một thử nghiệm, hãy bắt đầu bộ đếm từ 0 và cộng 1 khi thử nghiệm đúng.
- Bên dưới chúng ta đếm xem có bao nhiêu giá trị chẵn (
v % 2 == 0).
public class Main {
public static void main(String[] args) {
int[] a = {3, 4, 7, 10};
int evens = 0;
for (int v : a) {
if (v % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
Tìm giá trị lớn nhất
- Bắt đầu bằng cách giả sử giá trị đầu tiên là lớn nhất:
int max = a[0];. - Duyệt qua các giá trị còn lại. Nếu một giá trị lớn hơn
max, hãy gán nó làmmaxmới. - Cách này cũng hoạt động với số âm, vì giả thiết được lấy từ chính mảng đó.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
System.out.println(max); // 9
}
}
Tìm giá trị nhỏ nhất
- Giá trị nhỏ nhất sử dụng cùng cấu trúc — chỉ cần đảo ngược điều kiện kiểm tra thành
<. - Bắt đầu với
int min = a[0];và giữ lại giá trị nhỏ nhất bạn thấy. - Đừng bao giờ khởi tạo
minbằng 0; một giá trị thực tế từ mảng sẽ là giả thiết an toàn ban đầu.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
System.out.println(min); // 2
}
}
Tìm kiếm một giá trị
- Để tìm vị trí của một giá trị, hãy duyệt chỉ số và so sánh từng phần tử.
- Trả về chỉ số ngay khi bạn tìm thấy nó.
- Nếu vòng lặp kết thúc mà không có sự trùng khớp, trả về
-1để biểu thị "không tìm thấy".
public class Main {
public static void main(String[] args) {
int[] a = {5, 8, 13, 21};
int target = 13;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop at the first match
}
}
System.out.println(found); // 2
}
}
Trung bình cộng
- Trung bình = tổng chia cho số lượng. Số lượng là
a.length. - Để có kết quả thập phân, hãy chia cho
(double) a.length, tránh phép chia nguyên (integer division). (double)chuyển độ dài sang dạng thập phân trước khi thực hiện phép chia.
public class Main {
public static void main(String[] args) {
int[] a = {2, 3, 10};
int total = 0;
for (int v : a) {
total = total + v;
}
double avg = total / (double) a.length;
System.out.println(avg); // 5.0
}
}
Lỗi thường gặp
- Khởi tạo max hoặc min từ phần tử đầu tiên, sau đó so sánh với các phần tử còn lại.
- Đừng đọc vượt quá
a.length - 1.
Bây giờ bạn thử
- Mỗi nhiệm vụ hoàn thành một phương pháp mà Harness gọi với nhiều mảng khác nhau.
- Tái sử dụng các mẫu trên: tổng tích lũy, "tốt nhất tính đến thời điểm đó", hoặc bộ đếm.
- Sử dụng Check answer để biên dịch mã của bạn với các bài kiểm tra được cung cấp và xem kết quả. Giữ nguyên giao diện class và phương thức được hiển thị trong file khởi tạo.
Quét mảng để tìm giá trị lớn nhất
Một lượt duyệt giữ một tổng hợp max, cập nhật nó khi gặp một giá trị lớn hơn.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện max(int[] a) sao cho nó trả về giá trị lớn nhất trong mảng. Bạn có thể giả sử mảng có ít nhất một giá trị. Nó cũng phải hoạt động tốt với các số âm.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện countEven(int[] a) sao cho nó trả về số lượng các giá trị chẵn. Một giá trị được coi là chẵn khi v % 2 == 0. Mảng rỗng sẽ trả về 0.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện indexOf(int[] a, int target). Trả về chỉ mục của lần đầu tiên target xuất hiện. Nếu nó không có trong mảng, hãy trả về -1.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện average(int[] a). Trả về giá trị trung bình của các giá trị dưới dạng double. Chia cho (double) a.length để bạn có được số thập phân, tránh chia nguyên. Bạn có thể giả sử mảng không rỗng.
Nhấn Chạy để xem kết quả ở đây.