Algoritma ArrayList: filter dan bug penghapusan
Melakukan pekerjaan pada seluruh daftar
- Sekarang Anda dapat menyimpan data dalam an
ArrayList. Selanjutnya kita proses data tersebut. - Pekerjaan umum: hitung item yang sesuai aturan, filter mereka ke dalam daftar baru, dan hapus sebagian darinya.
- Semua ini menggunakan loop atas daftar.
Menghitung dengan aturan
- Lintasi daftar, uji setiap item, dan tambahkan
1ke penghitung ketika uji berhasil. n % 2 == 0bernilai benar jikangenap.n % 2 != 0bernilai benar jikanganjil.- Ini hanya membaca daftar, jadi enhanced for-loop sudah cukup.
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
}
}
Memfilter ke daftar baru
- Filtering hanya menyimpan item yang lolos uji.
- Pola yang aman: buat daftar baru kosong, lalu
addsetiap item yang lolos. - Daftar lama tidak berubah. Ini menghindari bug yang akan kita lihat selanjutnya.
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]
}
}
Bug remove-while-iterating
- Tampaknya mudah: loop maju dan
remove(i)item-item yang tidak diinginkan. - Namun,
remove(i)menggeser setiap item berikutnya satu posisi ke kiri. Loop kemudian menambahkan1keidan melewati item yang berpindah ke posisi lama. - Contoh di bawah mencoba menghapus semua genap tetapi melewatkan satu.
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
}
}
Mengapa melewatkan
- Mulai:
[2, 4, 5],i = 0.2genap, hapus. Daftar menjadi[4, 5]. - The
4turun ke index0. Tapi loop sekarang mengaturi = 1. - Di
i = 1kita melihat5, bukan4. The4tidak pernah diperiksa. Ia tetap ada.
Perbaikan: loop mundur
- Lintasi dari index terakhir turun ke
0. - Ketika Anda menghapus index
i, hanya item-item setelahiyang bergeser — dan Anda telah melewati item-item tersebut. - Indeks yang masih perlu dikunjungi adalah lebih kecil dari
i, jadi tidak ada yang bergerak menjauh dari Anda.
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
}
}
Catatan tentang enhanced for-loop
- Anda mungkin tergoda untuk menghapus di dalam
for (int x : nums). - Jangan. Mengubah ukuran daftar selama perulangan for-tingkat biasanya menyebabkan error
ConcurrentModificationException, dan ketika tidak terjadi, item akan dilewati secara diam-diam. Gunakan perulangan berbasis indeks sebagai gantinya. - Untuk menghapus, selalu gunakan loop indeks mundur di atas.
Kesalahan umum
- Menghapus saat looping maju berdasarkan indeks melewatkan item berikutnya (bug remove).
- Loop mundur, atau gunakan iterator, saat menghapus.
Sekarang Anda coba
- Setiap tugas telah mengisi kerangka class — tulis kode Anda di dalam main, atau lengkapi method yang ditampilkan.
- Gunakan Periksa jawaban untuk mengompilasi kode Anda dengan tes yang disediakan dan lihat hasilnya. Jaga antarmuka kelas dan metode yang ditampilkan pada starter.
- Kode Anda dikompilasi dan dijalankan di server, sehingga bahkan jalankan pertama kali pun cepat.
Memfilter daftar
Menghapus saat perulangan menggeser indeks — telusuri untuk melihat alasannya.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi countOdds(ArrayList<Integer> a) agar mengembalikan berapa banyak angka dalam daftar yang ganjil. Suatu angka adalah ganjil ketika x % 2 != 0.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi keepPositives(ArrayList<Integer> a). Bangun dan kembalikan ArrayList<Integer> baru yang hanya berisi angka-angka yang lebih besar dari 0, dalam urutan aslinya. Jangan ubah a.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi removeEvens(ArrayList<Integer> a) agar menghapus setiap angka genap dari a itu sendiri. Loop mundur berdasarkan indeks agar Anda tidak melewatkan item. Kembalikan sesuatu (void).
Klik Jalankan untuk melihat output di sini.