Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/move-zeroes/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một mảng số nguyên nums, di chuyển toàn bộ số 0 có trong mảng về vị trí cuối mảng nhưng không được thay đổi thứ tự của các phần tử khác.
Lưu ý rằng bạn phải thực hiện việc này mà không tạo bản sao của mảng.

Điều kiện:

  • 1 <= nums.length <= 10^4.
  • -231 <= nums[i] <= 231 - 1.

Ví dụ 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Ví dụ 2:

Input: nums = [0]
Output: [0]

3. Phân tích

Ố kề, bài này tuy không quá phức tạp, nhưng đề bài yêu cầu chúng ta không được tạo ra một mảng khác, rồi sắp xếp mảng đó, mà ta phải thực hiện việc sắp xếp ngay trên mảng nums. Để làm được bài này chúng ta sẽ sử dụng kĩ thuật hai con trỏ. Với một con trỏ i chạy như bình thường từ đầu tới cuối mảng và một con trỏ k luôn trỏ tới vị trí của phần tử là 0.
Khi i chạy đến phần tử khác 0, ta sẽ tạo ra một biến t chứa giá trị khác 0 của i;
i thì gán giá trị của k, tức đang là 0;
và rồi k thì lại lấy giá trị của t.

Làm như vậy để đổi chỗ những phần tử 0 lên trước, số 0 thì đổi chỗ cho phần tử đó, nhưng vẫn không thay đổi thứ tự của những phần tử khác 0.
Sau khi đổi chỗ xong, ta sẽ cho k tiến thêm 1, để nó lại tiếp tục trỏ vào vị trí của phần tử 0.

Done! Tới bước tiếp theo.

4. Chạy code bằng cơm

Đầu tiên, ta có i với k đều có index = 0, lúc này k đang ở đúng vị trí rồi, ta không làm gì, còn nums[i] = 0 thì ta cho i tiếp tục di chuyển.
leetcode-283-1

Khi này tại i = 1 thì nums[i] = 1, mà 1 != 0 nên ta bắt đầu thực hiện công việc đổi chỗ.
leetcode-283-2

Sau khi đổi chỗ xong các bạn nhớ cho k++ để tiến thêm 1 nhé.

Lúc này khi i = 2 thì nums[i] = 0 ta lại cho i tiếp tục di chuyển.
leetcode-283-3

Tại i = 3 thì nums[i] = 3, ta lại thực hiện công việc đổi chỗ:
leetcode-283-4

Sau khi đổi chỗ thì nó sẽ trông như này:
leetcode-283-5

Thực hiện xong việc đổi chỗ nhớ cho k++ nhé, tiếp theo i sẽ nhảy đến phần tử cuối cùng. Tại đây, nums[i] = 12 cũng khác 0, ta lại thực hiện việc đổi chỗ:
leetcode-283-6

Sau khi đổi chỗ xong thì mảng nums trông như này:
leetcode-283-7

Vậy là chúng ta đã đưa hết tất cả số 0 về cuối mảng mà không làm thứ tự các phần tử khác thay đổi.

5. Code bằng máy

Code của chúng ta sẽ như sau:

 public void moveZeroes(int[] nums) {
     for (int i = 0, k = 0; i < nums.length; i++) {
         if(nums[i] != 0){
             int t = nums[i];
             nums[i] = nums[k];
             nums[k] = t;
             k++;
         }
     }
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!