LeetCode 0283

Hung NguyenAbout 2 min

0283. Move Zeroes

Thẻ: Array, Two Pointers
Độ khó: Dễ

Đề bài

Mô tả: Cho một mảng số nguyên $nums$ .

Yêu cầu: Di chuyển tất cả các số $0$ về cuối mảng và duy trì thứ tự tương đối của các số khác $0$ .

Giải thích:

Chỉ được thực hiện trên mảng gốc.
$1 \le \text{nums.length} \le 10^4$ .
$-2^{31} \le \text{nums[i]} \le 2^{31} - 1$ .

Ví dụ:

Ví dụ 1:

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

Ví dụ 2:

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

Ý tưởng

Ý tưởng 1: Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng của thuật toán là sử dụng sắp xếp nổi bọt để di chuyển các số $0$ về cuối mảng.

Chúng ta có thể sử dụng ý tưởng của thuật toán sắp xếp nổi bọt để di chuyển các phần tử có giá trị $0$ về cuối mảng.

Vì kích thước dữ liệu là $10^4$ , và độ phức tạp thời gian của thuật toán sắp xếp nổi bọt là $O(n^2)$ . Vì vậy, phương pháp này sẽ gây ra thời gian chạy quá lâu.

Ý tưởng 2: Con trỏ kép

Sử dụng hai con trỏ $slow$ và $fast$ . $slow$ trỏ đến cuối mảng các số khác $0$ đã được xử lý, $fast$ trỏ đến phần tử hiện tại đang xử lý.

Di chuyển con trỏ $fast$ từ trái sang phải, mỗi khi gặp phần tử khác $0$ , hoán đổi giá trị của con trỏ $slow$ và $fast$ , đồng thời di chuyển con trỏ $slow$ sang phải.

Khi kết thúc vòng lặp, tất cả các số $0$ đã được di chuyển về phía cuối mảng và vẫn duy trì được thứ tự tương đối của các số khác $0$ .

Giải pháp

Giải pháp 1: Sắp xếp nổi bọt (Bubble Sort)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            for j in range(len(nums) - i - 1):
                if nums[j] == 0 and nums[j + 1] != 0:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

Giải pháp 2: Con trỏ kép

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1