אלגוריתמים ב-ArrayList: סינון ובעיית ההסרה
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
ביצוע פעולות על רשימה שלמה
- כעת ניתן לאחסן נתונים ב-
ArrayList. בפעם הבאה נעשה עיבוד עליהם. - משימות נפוצות: ספירה של פריטים העונים לתנאי מסוים, סינון שלהם לרשימה חדשה, והסרת חלק מהם.
- כולם משתמשים במעגל על הרשימה.
ספירה עם כלל
- הליכה על הרשימה, בדיקת כל פריט, והוספת
1למניין כאשר הבדיקה מתאמת. n % 2 == 0מתאמת כאשרnהוא זוגי.n % 2 != 0מתאמת כאשרnהוא אי-זוגי.- כאן רק נקראים את הרשימה, ולכן מעגל for משופר מתאים.
English
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
}
}
סינון לרשימה חדשה
- סינון משאיר רק את הפריטים שעברו את הבדיקה.
- דפוס בטוח: יצירת רשימה ריקה חדשה, ולאחר מכן
addכל פריט שעובר את הבדיקה. - הרשימה הישנה אינה משתנה. הדבר נמנע מהשגיאה שנתראה בהמשך.
English
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ודולג על הפריט שעבר למקום הקודם. - הדוגמה להלן מנסה להסיר את כול הזוגיים אך מחמיצה אחד.
English
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
}
}
מדוע הדילוג מתרחש
- התחלה:
[2, 4, 5],i = 0.2הוא זוגי, הסרתו. הרשימה הופכת ל[4, 5]. - ה
4החליק מטה לתוך האינדקס0. אך המעגל כעת מגדיר אתi = 1. - ב
i = 1אנו מסתכלים על5, לא על4. ה4לא נבדק לעולם. הוא נשאר ברשימה.
התיקון: מעגל אחורה
- הליכה מהאינדקס האחרון כלפי מטה עד
0. - כאשר מסירים את האינדקס
i, רק פריטים אחריiזזים — ואנו כבר עברנו אותם. - האינדקסים שאתה עדיין צריך לבקר בהם הם קטנים מ-
i, ולכן אף דבר לא יזוז מתחתך.
English
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
}
}
הערה על מחזור for משופר
- ייתכן שתחשה לנקות בתוך
for (int x : nums). - אל תעשה זאת. שינוי גודל הרשימה במהלך for-Loop מוגבר בדרך כלל זורק
ConcurrentModificationException, וכאשר זה לא קורה, פריטים מוחרגים בשקט. השתמש במקום זאת במחזור אינדקס. - עבור מחיקה, השתמש תמיד במחזור אינדקס אחורי כפי שצוין למעלה.
טעויות נפוצות
- מחיקה בעת סיור קדמי לפי אינדקס מדלג על הפריט הבא (שגיאת ההסרה).
- סור באופן אחורי, או השתמש באיטרטור, בעת מחיקה.
כעת תנסו בעצמכם
- כל משימה ממלאת מראש את שלד המחלקה — כתוב את הקוד שלך בתוך main, או השלם את השיטה המוצגת.
- השתמשו ב-Check answer כדי לקמפיל את הקוד שלך עם הבדיקות הסופקות ולצפות בתוצאות. שמרו את ממשקי המחלקה והשיטה המוצגים בתחילת העבודה.
- הקוד שלך נרכב ונרץ על השרת, ולכן גם ההפעלה הראשונה היא מהירה.
חקור
סינון רשימה
הסרה בזמן סיור גורמת להזזת אינדקסים — צעד אחורה כדי להבין מדוע.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם countOdds(ArrayList<Integer> a) כך שיחזיר כמה מספרים ברשימה הם אי-זוגיים. מספר הוא אי-זוגי כאשר x % 2 != 0.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם keepPositives(ArrayList<Integer> a). בנה והחזר רשימה חדשה ArrayList<Integer> שמכילה רק מספרים גדולים מ0, בסדר המקורי שלהם. אל תשנה את a.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם removeEvens(ArrayList<Integer> a) כך שיסיר כל מספר זוגי ממערך a עצמו. טפל אחורה באינדקס כדי לא לדלג על פריטים. אל תחזיר דבר (void).
לחץ על הרץ כדי לראות את התוצא כאן.