Rotate array artinya memindahkan k nilai terakhir ke depan. Misalnya, rotate [1,2,3,4,5,6,7] ke kanan sebanyak 3 menghasilkan [5,6,7,1,2,3,4]. Tantangannya adalah melakukannya secara in place, tanpa array kedua.
Aku membandingkan penyalinan, penelusuran cycle rotasi, dan pembalikan segmen. Aku lebih suka versi reversal karena setiap dari tiga operasinya bisa diperiksa secara terpisah.
Baseline dengan copy
Versi ini menaruh setiap value di array baru, lalu menyalin hasilnya kembali:
function rotateNaive(nums, k) {
const n = nums.length;
if (n <= 1) return nums;
k = k % n;
const rotated = new Array(n);
// Just put each element where it should go
for (let i = 0; i < n; i++) {
rotated[(i + k) % n] = nums[i];
}
// Copy back to original
for (let i = 0; i < n; i++) {
nums[i] = rotated[i];
}
}
Mengisi rotated dan menyalinnya kembali butuh dua pass linear, jadi waktunya O(n). Array tambahan itu memakai O(n) space.
Percobaan cyclic in place dan biayanya
Lalu aku mencoba memindahkan setiap nilai langsung ke tujuannya dengan mengikuti cycle rotasinya:
function rotateCyclic(nums, k) {
const n = nums.length;
if (n <= 1) return nums;
k = k % n;
let count = 0;
let start = 0;
while (count < n) {
let current = start;
let temp = nums[start];
// Follow the rotation cycle
while (true) {
const next = (current + k) % n;
const nextTemp = nums[next];
nums[next] = temp;
temp = nextTemp;
current = next;
count++;
if (current === start) break;
}
start++;
}
}
Versi cyclic memakai O(1) extra space dan tetap menyentuh setiap elemen sekali. Menurut aku control flow-nya lebih susah diikuti. Loop while (count < n) membungkus loop while (true). Setiap cycle berakhir ketika if (current === start) break dijalankan. Variabel count, start, current, temp, next, dan nextTemp semuanya berukuran konstan, tapi satu off by one error aja bisa merusak hasilnya.
Loop luar while (count < n) berhenti setelah n perpindahan, termasuk ketika rotasi punya beberapa cycle terpisah. Total biayanya O(n) waktu dan O(1) extra space.
Tiga kali reversal
Ide in place yang lebih simpel adalah me-reverse seluruh array, me-reverse k nilai pertama, lalu me-reverse sisa nilainya. Untuk [1,2,3,4,5] yang di-rotate ke kanan sebanyak 2:
[5,4,3,2,1] setelah semuanya di-reverse, [4,5,3,2,1] setelah dua nilai pertama di-reverse, dan [4,5,1,2,3] setelah sisanya di-reverse.
Urutan langkah itu menaruh k nilai terakhir dari array asli di depan dan mengembalikan urutannya:
function rotate(nums, k) {
const n = nums.length;
if (n <= 1) return nums;
k = k % n;
if (k === 0) return nums;
// Step 1: Flip entire array
let start = 0;
let end = n - 1;
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
// Step 2: Flip first k elements
start = 0;
end = k - 1;
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
// Step 3: Flip remaining n-k elements
start = k;
end = n - 1;
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
Rotasi ke kanan mengambil k nilai terakhir dan memindahkannya ke depan n-k nilai pertama. Reversal penuh menukar posisi kedua kelompok itu dan membalik urutan di dalam setiap kelompok. Me-reverse setiap kelompok secara terpisah membetulkan urutan di dalam kelompoknya.
Ketiga loop itu melakukan paling banyak n/2 + k/2 + (n-k)/2 = n swap. Dengan batas loop berupa integer, jumlah pastinya adalah floor(n/2) + floor(k/2) + floor((n-k)/2), dan tetap O(n). Algoritma ini cuma menyimpan start, end, temp, n, dan k. Jadi, algoritma ini butuh O(n) time dan O(1) extra space. Yang disentuh cuma array aslinya.
Biaya reversal dan perbandingannya
| Pendekatan | Time Complexity | Space Complexity | Kompleksitas Kode | Maintainability |
|---|---|---|---|---|
| Naive (copy array) | O(n) | O(n) | Rendah | Tinggi |
| Pendekatan cyclic | O(n) | O(1) | Sangat Tinggi | Rendah |
| Three-step reversal | O(n) | O(1) | Rendah | Tinggi |
Ketiga pendekatan butuh O(n) time. Versi copy memakai O(n) space, sedangkan versi cyclic dan reversal memakai O(1). Aku lebih suka reversal karena state-nya cuma beberapa index dan ketiga operasinya gampang diperiksa.
Merotasi array contoh
const nums = [1, 2, 3, 4, 5, 6, 7];
console.log("Before:", nums);
rotate(nums, 3);
console.log("After:", nums); // [5, 6, 7, 1, 2, 3, 4]
Contoh ini menghasilkan [5, 6, 7, 1, 2, 3, 4] secara in place.

Memuat komentar...