Array algorithms: max, count, search, average · Thuật toán mảng: tìm max, đếm, tìm kiếm, trung bình
Common array jobs
- Some array tasks come up again and again: find the sum, the biggest, the smallest, or count items.
- Each one uses the same idea: start with a guess, then loop and update it.
- These patterns appear all the time on the AP CSA exam.
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.
Sum and count
- Keep a running total that starts at 0, and add each value.
- To count items that pass a test, start a counter at 0 and add 1 when the test is true.
- Below we count how many values are even (
v % 2 == 0).
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
}
}
Find the maximum
- Start by guessing the first value is the biggest:
int max = a[0];. - Loop through the rest. If a value is bigger than
max, make it the newmax. - This works for negative numbers too, because the guess comes from the array itself.
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
}
}
Find the minimum
- The minimum uses the same shape — just flip the test to
<. - Start with
int min = a[0];and keep the smallest value you see. - Never start
minat 0; a real value from the array is a safe first guess.
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
}
}
Search for a value
- To find where a value is, loop the index and compare each element.
- Return the index as soon as you find it.
- If the loop finishes with no match, return
-1to mean "not found".
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
}
}
Average
- Average = sum divided by count. The count is
a.length. - To get a decimal, divide by
(double) a.length, so the math is not integer division. (double)turns the length into a decimal before the division.
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
}
}
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past
a.length - 1.
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.
Now you try
- Each task completes a method the Harness calls with several arrays.
- Reuse the patterns above: a running total, a "best so far", or a counter.
- Press Run to compile, then Check answer.
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.
- Nhấn Run để biên dịch, sau đó nhấn Check answer.
Scanning an array for the max · Quét mảng để tìm giá trị lớn nhất
One pass keeps a running max, updating it when a bigger value appears. · 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.
Complete max(int[] a) so it returns the largest value in the array. You may assume the array has at least one value. It must work with negative numbers too. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete countEven(int[] a) so it returns how many values are even. A value is even when v % 2 == 0. An empty array returns 0. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete indexOf(int[] a, int target). Return the index of the first time target appears. If it is not in the array, return -1. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete average(int[] a). Return the average of the values as a double. Divide by (double) a.length so you get a decimal, not integer division. You may assume the array is not empty. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.