Arrays: Left Rotation – HackerRank Solution

Tiếp tục với Series giải các bài toán trong bộ Interview Preparation Kit của Hackerrank, chúng ta sẽ giải một bài về mảng có tựa đề là Arrays: Left Rotation.

Tác giả: Heraldo

Độ khó: Dễ

Điểm: 20

Link bài toán: HackerRank – Left Rotation

Dyno Nguyen Interview Preparation Kit - Hackerrank

Đề bài toán Left Rotation

Dyno Nguyen - Arrays: Left Rotation - HackerRank Solution
Dyno Nguyen - Arrays: Left Rotation - HackerRank Solution - Sample input

Tóm tắt đề bài

Đầu vào (input)

  • Mảng một chiều arrn phần tử
  • 1 <= n <= 105
  • 1 <= d <= n
  • 1 <= arr[i] <= 106

Giải thích (Explanation)

  • Chúng ta nhận vào một mảng có n phần tử, số d lần xoay.
  • Nhiệm vụ chúng ta đơn giản là xoay mảng trái mảng đó d lần

Ý tưởng và Triển khai

Giải đơn giản

  • Mỗi lần xoay thì chúng ta sẽ đưa phần tử đó về cuối và dịch tất cả các phần tử ở trên lên 1 vị trí.
  • Cứ thế ta thực hiện xoay d lần là xong.
function rotLeft(arr, d) {
    const len = arr.length;
    
    // Lặp qua d lần, tương đương d lần xoay mảng
    for(let i = 0; i < d; ++i){
        // lưu lại phần tử đầu
        let t = arr[0];
        
        // Dịch tất cả các phần tử lên đầu
        // Trong JS chúng ta có thể dùng splice để xoá 1 phần tử đi
        arr.splice(0, 1);
        
        // Thêm phần tử đầu lúc nãy vào cuối mảng
        arr.push(t);
    }

    return arr;
}

Phân tích:

Với cách trên, mặc dù vẫn có thể pass qua tất cả các test case, nhưng chúng ta sẽ thấy cách này vẫn chưa được tối ưu. Và thấy được có một vài test case sẽ chạy rất chậm (gần như là time out) vì số lượng phần tử mảng khá lớn và d cũng lớn. Độ phức tạp O(d).

Vì thế, cùng mình giải cách khác tối ưu hơn tí nhé.

Giải tối ưu

  • Case 1: d =n thì Nếu số lần xoay d mà bằng số phần tử của mảng thì chúng ta sẽ nhận được mảng ban đầu (không cần xoay).
  • Case 2: d > n thì chúng ta chỉ cần xoay đúng phần dư của d/n là được, lúc này d = d % n. Nhưng trong bài này điều kiện cho là d <= n nên chúng ta không cần xét đến.
  • Case 3: d < n Nếu để ý thì chúng ta có thể thấy là ta chỉ cần cắt mảng ban đầu thành 2 mảng con. Một mảng có d phần tử và mảng còn lại n-d phần tử. Sau đó đảo 2 mảng đó lại là xong.
  • Từ đó, độ phức tạp chỉ còn O(1).
Dyno Nguyen left rotation giai toi uu
function rotLeft(arr, d) {
  let len = arr.length;

  // Case 1
  if (d === len) return [...arr];

  // Case 3
  const arr1 = arr.slice(0, d);
  const arr2 = arr.slice(d, len);

  return [...arr2, ...arr1];
}

Tạm kết

Bài này đơn giản chỉ vậy thôi. Rất cảm ơn bạn đã đọc bài viết ❤

Nếu còn cách giải nào hay ho khác hãy comment phía dưới cho mình biết với nhé và hãy theo dõi Series phá đảo Hackerrank của mình để cùng luyện tập nhiều bài khác hơn nhé.

Bạn có thể đọc thêm:

Give a Comment