Teknik Dua Pointer Java

1. Ikhtisar

Dalam tutorial ini, kita akan membahas pendekatan dua penunjuk untuk memecahkan masalah yang melibatkan array dan daftar. Teknik ini adalah cara yang mudah dan efisien untuk meningkatkan performa algoritme kami.

2. Deskripsi Teknik

Dalam banyak masalah yang melibatkan array atau daftar, kita harus menganalisis setiap elemen dari array tersebut dibandingkan dengan elemen lainnya.

Untuk mengatasi masalah seperti ini kita biasanya mulai dari indeks pertama dan mengulang melalui array satu kali atau lebih tergantung pada implementasi kita. Terkadang, kami juga harus membuat larik sementara tergantung pada persyaratan masalah kami.

Pendekatan di atas mungkin memberi kita hasil yang benar, tetapi kemungkinan besar tidak akan memberi kita solusi yang paling hemat ruang dan waktu.

Akibatnya, sering kali baik untuk mempertimbangkan apakah masalah kita dapat diselesaikan secara efisien dengan menggunakan pendekatan dua poin .

Dalam pendekatan dua penunjuk, penunjuk merujuk ke indeks array. Dengan menggunakan pointer, kita dapat memproses dua elemen per loop, bukan hanya satu.

Pola umum dalam pendekatan dua penunjuk melibatkan:

  • Dua petunjuk masing-masing dimulai dari awal dan akhir hingga keduanya bertemu
  • Satu penunjuk bergerak dengan kecepatan lambat sementara penunjuk lainnya bergerak dengan kecepatan lebih cepat

Kedua pola di atas dapat membantu kita mengurangi kompleksitas waktu dan ruang dari masalah kita karena kita mendapatkan hasil yang diharapkan dalam iterasi yang lebih sedikit dan tanpa menggunakan terlalu banyak ruang tambahan.

Sekarang, mari kita lihat beberapa contoh yang akan membantu kita memahami teknik ini lebih baik.

3. Jumlah Ada dalam Array

Masalah: Mengingat array bilangan bulat yang diurutkan, kita perlu melihat apakah ada dua angka di dalamnya sehingga jumlahnya sama dengan nilai tertentu.

Misalnya, jika larik input kita adalah [1, 1, 2, 3, 4, 6, 8, 9] dan nilai targetnya adalah 11 , maka metode kita harus mengembalikan true . Namun, jika nilai target adalah 20 , seharusnya menghasilkan false .

Mari kita lihat solusi naif terlebih dahulu:

public boolean twoSumSlow(int[] input, int targetValue) { for (int i = 0; i < input.length; i++) { for (int j = 1; j < input.length; j++) { if (input[i] + input[j] == targetValue) { return true; } } } return false; }

Dalam solusi di atas, kami mengulang array masukan dua kali untuk mendapatkan semua kemungkinan kombinasi. Kami memeriksa jumlah kombinasi terhadap nilai target dan mengembalikan true jika cocok. Kompleksitas waktu dari solusi ini adalah O (n ^ 2) .

Sekarang mari kita lihat bagaimana kita bisa menerapkan teknik dua-penunjuk di sini:

public boolean twoSum(int[] input, int targetValue) { int pointerOne = 0; int pointerTwo = input.length - 1; while (pointerOne < pointerTwo) { int sum = input[pointerOne] + input[pointerTwo]; if (sum == targetValue) { return true; } else if (sum < targetValue) { pointerOne++; } else { pointerTwo--; } } return false; }

Karena array sudah diurutkan, kita bisa menggunakan dua pointer. Satu penunjuk dimulai dari awal larik, dan penunjuk lainnya dimulai dari akhir larik, lalu kami menambahkan nilai pada penunjuk ini. Jika jumlah nilai kurang dari nilai target, kami menambah penunjuk kiri, dan jika jumlahnya lebih tinggi dari nilai target, kami mengurangi penunjuk kanan.

Kami terus memindahkan petunjuk ini sampai kami mendapatkan jumlah yang cocok dengan nilai target atau kami telah mencapai tengah larik, dan tidak ada kombinasi yang ditemukan. Kompleksitas waktu dari solusi ini adalah O (n) dan kompleksitas ruang adalah O (1) , peningkatan yang signifikan dari implementasi pertama kami.

4. Putar Array k Langkah

Masalah: Diberikan sebuah array, putar array ke kanan sebanyak k langkah, di mana k bukan negatif. Misalnya, jika larik masukan kita adalah [1, 2, 3, 4, 5, 6, 7] dan k adalah 4 , maka keluarannya harus [4, 5, 6, 7, 1, 2, 3] .

Kita bisa menyelesaikan ini dengan membuat dua loop lagi yang akan membuat kompleksitas waktu menjadi O (n ^ 2) atau dengan menggunakan array tambahan sementara, tetapi itu akan membuat kompleksitas ruang menjadi O (n) .

Mari kita selesaikan ini menggunakan teknik dua penunjuk sebagai gantinya:

public void rotate(int[] input, int step) { step %= input.length; reverse(input, 0, input.length - 1); reverse(input, 0, step - 1); reverse(input, step, input.length - 1); } private void reverse(int[] input, int start, int end) { while (start < end) { int temp = input[start]; input[start] = input[end]; input[end] = temp; start++; end--; } }

Dalam metode di atas, kami membalik bagian dari array input di tempat, beberapa kali, untuk mendapatkan hasil yang diinginkan. Untuk membalik bagian, kami menggunakan pendekatan dua penunjuk di mana pertukaran elemen dilakukan di kedua ujung bagian larik.

Secara khusus, pertama-tama kita membalikkan semua elemen array. Kemudian, kita membalikkan k elemen pertama diikuti dengan membalikkan elemen lainnya. Kompleksitas waktu dari solusi ini adalah O (n) dan kompleksitas ruang adalah O (1) .

5. Elemen Tengah dalam LinkedList

Masalah: Diberikan LinkedList tunggal , temukan elemen tengahnya. Misalnya, jika input LinkedList kita adalah 1-> 2-> 3-> 4-> 5, maka outputnya harus 3 .

Kita juga bisa menggunakan teknik dua penunjuk dalam struktur data lain yang mirip dengan array seperti LinkedList :

public  T findMiddle(MyNode head) { MyNode slowPointer = head; MyNode fastPointer = head; while (fastPointer.next != null && fastPointer.next.next != null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }

Dalam pendekatan ini, kami melintasi daftar tertaut menggunakan dua petunjuk. Satu penunjuk bertambah satu sementara yang lain bertambah dua. Saat penunjuk cepat mencapai akhir, penunjuk lambat akan berada di tengah daftar tertaut. Kompleksitas waktu dari solusi ini adalah O (n) , dan kompleksitas ruang adalah O (1) .

6. Kesimpulan

Dalam artikel ini, kita membahas bagaimana kita bisa menerapkan teknik dua penunjuk dengan melihat beberapa contoh dan melihat bagaimana itu meningkatkan efisiensi algoritma kita.

Kode dalam artikel ini tersedia di Github.