อัลกอริทึมของ ArrayList: การกรองและข้อผิดพลาดในการลบ
การทำงานกับทั้งรายการ
- Now you can store data in an
ArrayList. Next we process it. - งานทั่วไป: นับ รายการที่ตรงกับเงื่อนไข, กรอง รายการเหล่านั้นลงในรายการใหม่ และ ลบ รายการบางรายการออก
- ทั้งหมดนี้ใช้ลูปวนรอบรายการ
การนับด้วยกฎ
- เดินผ่านรายการ ทดสอบแต่ละองค์ประกอบ และเพิ่ม
1ไปยังตัวนับเมื่อการทดสอบเป็นจริง n % 2 == 0เป็นจริงเมื่อnเป็น คู่n % 2 != 0เป็นจริงเมื่อnเป็น คี่- สิ่งนี้เพียง read รายการ ดังนั้น enhanced for-loop ก็เพียงพอแล้ว
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
}
}
การกรองเข้ารายการใหม่
- Filtering เก็บไว้เฉพาะองค์ประกอบที่ผ่านการทดสอบ
- รูปแบบที่ปลอดภัย: สร้าง ลิสต์ว่าง ใหม่ แล้ว
addรายการที่ผ่านเกณฑ์เข้าไป - รายการเก่าไม่ถูกเปลี่ยน สิ่งนี้จะหลีกเลี่ยง bug ที่เราจะเห็นต่อไป
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]
}
}
บั๊กการลบขณะวนลูป
- ดูง่าย:วนลูปไปข้างหน้าและ
remove(i)รายการที่ไม่ต้องการออก - แต่
remove(i)จะเลื่อนรายการทั้งหมดที่อยู่ถัดมา หนึ่งตำแหน่งไปทางซ้าย จากนั้นลูปจะเพิ่ม1เข้ากับiและ ข้าม รายการที่เคลื่อนเข้ามาอยู่ในตำแหน่งเดิม - ตัวอย่างด้านล่างพยายามลบเลขคู่ทั้งหมดแต่ misses หนึ่งตัว
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
}
}
ทำไมถึง skip
- Start:
[2, 4, 5],i = 0.2is even, remove it. List becomes[4, 5]. - The
4slid down into index0. But the loop now setsi = 1. - At
i = 1we look at5, not4. The4was never checked. It stays in.
The fix: loop backwards
- Walk from the last index down to
0. - เมื่อคุณลบดัชนี
iรายการที่อยู่ หลังiเท่านั้นที่จะเลื่อนตำแหน่ง — ซึ่งคุณได้ผ่านรายการเหล่านั้นไปแล้ว - ดัชนีที่คุณยังต้องเข้าถึงมีค่าน้อยกว่า
iดังนั้นไม่มีอะไรเคลื่อนที่ออกจากพื้นที่ของคุณ
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
}
}
A note on the enhanced for-loop
- You may be tempted to remove inside
for (int x : nums). - ห้ามทำ การเปลี่ยนขนาดลิสต์ระหว่าง enhanced for-loop มักจะทำให้เกิด
ConcurrentModificationExceptionและเมื่อไม่เกิด รายการจะถูกข้ามอย่างเงียบๆ ให้ใช้ index loop แทน - สำหรับการลบ ให้ใช้ backward index loop ข้างบนเสมอ
ข้อผิดพลาดที่พบบ่อย
- การลบขณะวนลูปไปข้างหน้าด้วย index จะทำให้ข้ามรายการถัดไป (บักการลบ)
- Loop backwards, or use an iterator, when removing.
ลองดูเลย
- Each task เติม skeleton class ไว้ล่วงหน้า — เขียนโค้ดของคุณ ภายใน main, หรือเติมเต็ม method ที่แสดง
- ใช้ Check answer เพื่อ compile โค้ดของคุณพร้อมทดสอบด้วย test ที่กำหนดและดูผลลัพธ์ รักษาโครงสร้าง class และ method ตามที่แสดงในไฟล์เริ่มต้น
- โค้ดของคุณ compile และ run บน server, ดังนั้นแม้การ run ครั้งแรกก็เร็ว
การกรอง (filtering) list
การลบขณะวนลูปจะทำให้ดัชนีเลื่อน — ลองตามขั้นตอนเพื่อดูว่าทำไมถึงเป็นแบบนั้น
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม countOdds(ArrayList<Integer> a) ให้กลับค่า จำนวน จำนวนเต็มในลิสต์ที่เป็นเลขคี่ จำนวนเต็มจะเป็นเลขคี่เมื่อ x % 2 != 0
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม keepPositives(ArrayList<Integer> a) สร้างและกลับค่า ลิสต์ ArrayList<Integer> ใหม่ที่เก็บเฉพาะตัวเลขที่มีค่ามากกว่า 0 โดยคงลำดับเดิมไว้ อย่า แก้ไข a
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม removeEvens(ArrayList<Integer> a) เพื่อลบ ทุก เลขคู่ออกจาก a โดยตรง วนลูป ย้อนกลับ ตามดัชนีเพื่อไม่ให้ข้ามรายการ กลับค่าอะไรเลย (void)
คลิก Run เพื่อดูผลลัพธ์ที่นี่