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/shuffle-the-array/
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 và số nguyên n, mảng nums có kích thước là 2n và có dạng [x1,x2,...,xn,y1,y2,...,yn].
Trả về kết quả là mảng sắp xếp theo dạng [x1,y1,x2,y2,...,xn,yn].
Điều kiện:
1 <= n <= 500.nums.length == 2n.1 <= nums[i] <= 10^3.
Bài toán minh họa 1:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Bài toán minh họa 2:
Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]
Bài toán minh họa 3:
Input: nums = [1,1,2,2], n = 2
Output: [1,2,1,2]
3. Phân tích
Ô kê các bạn, bài này cũng không quá phức tạp lắm đâu. Định dạng ban đầu của mảng nums là [x1,x2,...,xn,y1,y2,...,yn], giờ chúng ta cần phải trả về mảng theo dạng [x1,y1,x2,y2,...,xn,yn].
Điều quan trọng ở đây chính là số n, chúng ta sẽ bổ cái mảng nums kia ra tại vị trí n, hay nói là chia đôi cũng được, tại vì kích thước của mảng nums luôn là số chẵn mà.
Chúng ta sẽ cần một mảng mới hứng kết quả có được, với phần tử sẽ là [x1, y1, x2, y2, ...] với x là những phần tử đứng trước n vafy là những phần tử đứng sau n:
Nhìn hơi rối mắt đúng không? Nhưng nếu các bạn để ý, những phần tử x khi xếp vào mảng mới luôn nằm ở vị trí index là số chẵn, và y thì luôn nằm ở vị trí index là số lẻ. Như vậy, công việc của ta cần làm chỉ là:
Khi gặp index của mảng mới là số chẵn, ta thêm số x, gặp index lẻ thì ta thêm số y. Vậy là xong!
4. Code chạy bằng cơm
Đầu tiên chúng ta cần một mảng mới để chứa kết quả, có kích thước là 2n, hoặc kích thước chính bằng mảng nums cũng được, vì số lượng phần tử không thay đổi:
Tiếp theo chúng ta sẽ duyệt qua mảng res này để thêm các phần tử vào đúng vị trí của nó. Tuy nhiên, con trỏ i sẽ không chạy hết qua mảng, mà sẽ chỉ chạy đến n mà thôi, bởi vì mảng num bị chia đôi tại n mà. Bên cạnh đó, bước nhảy của i sẽ phải là ++i chứ không phải i++ như thông thường:
Tại sao lại là ++i? Trước hết thì trong toán học, công thức của số chẵn sẽ là 2n và số lẻ sẽ là 2n + 1, dựa vào đó ta có thể định sẵn vị trí cho các phần tử mà ta muốn, mỗi một lần chúng ta sẽ thêm hai phần tử cùng một lúc vào mảng res, một số chẵn và một số lẻ liền sau nó. Chính vì thêm hai phần tử cùng một lúc nên khi đến lần lặp tiếp theo, ta phải cộng thêm 1 vào i trước rồi mới thực hiện thêm phần tử:
Done! Chúng ta sang bước tiếp theo!
5. Code bằng máy
Code của chúng ta sẽ như sau:
public int[] shuffle(int[] nums, int n) {
int[] res = new int[2 * n];
for (int i = 0; i < n; ++i) {
res[2 * i] = nums[i];
res[2 * i + 1] = nums[n+i];
}
return res;
}
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!!!
Bình luận