Thuật toán ArrayList: lọc và lỗi remove
Thực hiện tác vụ trên toàn bộ danh sách
- Bây giờ bạn có thể lưu dữ liệu vào một
ArrayList. Tiếp theo chúng ta sẽ xử lý nó. - Các công việc phổ biến: đếm các mục thỏa mãn quy tắc, lọc chúng vào danh sách mới, và loại bỏ một số mục.
- Tất cả những việc này đều sử dụng vòng lặp trên danh sách.
Đếm theo quy tắc
- Duyệt qua danh sách, kiểm tra từng mục, và cộng
1vào bộ đếm khi kiểm tra trả về true. n % 2 == 0là true khinlà chẵn.n % 2 != 0là true khinlà lẻ.- Việc này chỉ đọc danh sách, nên vòng lặp for nâng cao là đủ.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(4);
nums.add(7);
nums.add(10);
nums.add(3);
int evens = 0;
for (int x : nums) {
if (x % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
Lọc vào danh sách mới
- Lọc chỉ giữ lại các mục pass (thỏa mãn) bài kiểm tra.
- Mẫu an toàn: tạo một danh sách mới trống, sau đó
addmỗi mục pass. - Danh sách cũ không bị thay đổi. Điều này tránh lỗi chúng ta sẽ gặp ngay sau đây.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(4);
nums.add(7);
nums.add(10);
nums.add(3);
ArrayList<Integer> bigOnes = new ArrayList<Integer>();
for (int x : nums) {
if (x >= 5) {
bigOnes.add(x);
}
}
System.out.println(bigOnes); // [7, 10]
}
}
Lỗi remove-while-iterating (xóa trong lúc duyệt)
- Nó trông rất dễ: duyệt từ đầu và
remove(i)các mục bạn không muốn. - Nhưng
remove(i)sẽ đẩy mọi mục sau đó một bước sang trái. Vòng lặp sau đó tăng1lênivà bỏ sót mục vừa di chuyển vào vị trí cũ. - Ví dụ dưới đây cố gắng xóa tất cả các số chẵn nhưng bỏ sót một số.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(2);
nums.add(4); // this one gets skipped!
nums.add(5);
// BUGGY: forward loop while removing
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) % 2 == 0) {
nums.remove(i);
}
}
System.out.println(nums); // [4, 5] -- wrong, 4 was missed
}
}
Tại sao lại bỏ sót
- Ban đầu:
[2, 4, 5],i = 0.2là số chẵn, xóa nó. Danh sách trở thành[4, 5]. 4đã trượt xuống chỉ mục0. Nhưng vòng lặp giờ đây sẽ gáni = 1.- Tại
i = 1, ta nhìn vào5, không phải4.4đã không bao giờ được kiểm tra. Nó vẫn nằm trong danh sách.
Giải pháp: duyệt ngược
- Duyệt từ chỉ số cuối cùng xuống đến
0. - Khi bạn xóa chỉ số
i, chỉ các mục sauibị dịch chuyển — và bạn đã đi qua những mục đó rồi. - Các chỉ số bạn vẫn cần truy cập sẽ nhỏ hơn
i, nên không có mục nào bị đẩy khỏi vị trí của bạn.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(2);
nums.add(4);
nums.add(5);
// SAFE: backward loop while removing
for (int i = nums.size() - 1; i >= 0; i--) {
if (nums.get(i) % 2 == 0) {
nums.remove(i);
}
}
System.out.println(nums); // [5] -- correct
}
}
Lưu ý về vòng lặp for nâng cao
- Bạn có thể bị cám dỗ muốn xóa bên trong
for (int x : nums). - Không được. Thay đổi kích thước danh sách trong vòng lặp for-eenhanced thường gây ra lỗi
ConcurrentModificationException, và khi không có lỗi, các phần tử sẽ bị bỏ qua âm thầm. Hãy sử dụng vòng lặp chỉ số thay thế. - Đối với việc xóa, luôn sử dụng vòng lặp chỉ số ngược ở trên.
Lỗi thường gặp
- Xóa trong lúc duyệt từ đầu theo chỉ số sẽ bỏ sót mục tiếp theo (lỗi xóa).
- Hãy duyệt ngược, hoặc sử dụng iterator, khi cần xóa.
Bây giờ bạn thử
- Mỗi nhiệm vụ điền sẵn khung lớp — viết mã của bạn bên trong main, hoặc hoàn thành phương thức được hiển thị.
- 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.
- Mã của bạn được biên dịch và chạy trên máy chủ, vì vậy ngay cả lần chạy đầu tiên cũng rất nhanh.
Lọc một danh sách
Xóa phần tử trong khi duyệt làm dịch chuyển chỉ mục — hãy bước từng bước để thấy lý do tại sao.
Độ 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 countOdds(ArrayList<Integer> a) sao cho nó trả về số lượng các số lẻ trong danh sách. Một số được coi là lẻ khi x % 2 != 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 keepPositives(ArrayList<Integer> a). Tạo và trả về một ArrayList<Integer> mới chỉ chứa các số lớn hơn 0, giữ nguyên thứ tự ban đầu. Không thay đổi a.
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 removeEvens(ArrayList<Integer> a) sao cho nó xóa tất cả các số chẵn khỏi chính a. Duyệt ngược theo chỉ mục để không bỏ sót phần tử nào. Không trả về gì (void).
Nhấn Chạy để xem kết quả ở đây.