Tuần trước mình hơi lười chút nên ko viết series tuần vừa rồi. Do vậy tuần này ta sẽ tiếp tục với chủ đề mỗi tuần một bài toán Hacke… LeetCode.
Làm Hackerank nhiều hơi bức bối một chút nay đổi gió qua LeetCode giải trí chút. ( Nếu ai chưa biết thì LeetCode cũng là một trang web nổi tiếng để luyện code, CTDL, algorithms,… nổi tiếng như Hackerank. Đặc biệt về phần thi và cộng đồng tôi thấy tốt hơn Hackerank nhiều ).
Bài toán : Remove Duplicates from Sorted Array
Một bài toán Easy Level nhưng đừng bao giờ coi thường easy level trên leetcode nhé :).
Tóm tắt bài toán : Ta được cho một mảng array đã được sắp xếp nhưng trong đó có các số bị lặp. Nhiệm vụ của chúng ta là remove các phần tử lặp và trả về độ dài mảng mới. Nghe có vẻ ngon ăn nhỉ. Easy phết.
Tuy nhiên , nó có thêm điều kiện ràng buộc không được cấp phát thêm bộ nhớ cho một mảng mới phải chỉnh sửa trên mảng cũ và độ phức tạp không gian là O(1).
Solution : Hmm….Làm sao để ta có thể xóa phần tử lặp hay chính xác hơn là xét phần tử tức là số nào bị lặp mà không cần dùng một mảng phụ để lưu hoặc kiểm tra nhỉ. Cũng khoai phết đấy .
Thực ra thì có một cách giải quyết rất hay đối với bài toàn này mà không phải đánh đổi giữa Time Complexity với Memory Complexity.
Tôi sẽ show code rồi giải thích trên đó cho dễ hiểu !
Code Java:
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0)
return 0;
int rightIndex = 0;
for (int index =1;index<nums.length;index++){
if(nums[index] != nums[rightIndex]){
rightIndex++;
nums[rightIndex] = nums[index];
}
}
return rightIndex+1;
}
}
Đầu tiên ta sẽ xét xem mảng input có == 0 hay không . Có thì return 0 luôn.
Sau đó ta dùng 2 biến để duyệt mảng (giống như 2 con trỏ ) kiểm tra mảng của chúng ta. Với biến rightIndex chỉ đúng với index thì tương ứng với số nào trong mảng đã remove duplicate numbers nên nó sẽ bắt đầu bằng 0 với giá trị là số đầu tiên. Biến Index =1 đến length của mảng. Để kiểm tra xem số nào khác với số có chỉ số đúng hiện tại. Nếu khác thì ta tăng rightIndex lên 1 để vị trí số đúng tiếp theo bằng số mà ta đang so sánh. Tiếp tục lặp như vậy đên hết length.
Như vậy sau 1 vòng lặp ta đã có đúng thứ tự của mảng với ko có số lặp. với số cuối cùng mảng chuẩn có index = rightIndex;
=> length của mảng = rightIndex +1;
And DONE!
Đây là một trang web khá hay để luyện code. Mọi người có thể tham khảo thứ .
Chúc mọi người một tuần vui vẻ, học tập và làm việc hiệu quả ! 😀
