Kỹ thuật Partitioning Arrays là một kỹ thuật phổ biến để làm việc với Array. Ngoài phổ biến, kỹ thuật này cũng hữu ích trong rất nhiều trường hợp. Điển hình là implement thuật toán Quick Sort với pivot.

Bắt đầu từ Quick Sort thì sẽ hơi khó khăn, chính vì vậy Kieblog sẽ bắt đầu từ những bài toán cơ bản nhất của Partitioning Arrays. Từng bước một giúp các bạn hiểu sâu hơn về kỹ thuật này

Bắt đầu ngay thôi nào!

1. Từ bài toán cơ bản nhất

Question 1: You are given an array of integers. Rearrange the array so that all zeroes are at the beginning of the array.
For example, [4,2,0,1,0,3,0] -> [0,0,0,4,1,2,3]

Bạn được cung cấp một mảng số nguyên. Hãy sắp xếp lại mảng sao cho tất cả số không nằm phía đầu của array. Nhưng phần tử khác không nằm cuối của Array

Một số bạn sẽ bắt đầu bởi sort. Tuy nhiên sort có thể làm thay đổi vị trí của những phần tử khác 0. Lúc này 4,1,2,3 lại thành 1,2,3,4. Không đúng.

Trường hợp thứ hai, nếu for loop trên Array để tìm các phần tử bằng 0 và khác 0 rồi sắp xếp. Độ phức tạp lúc này sẽ là O(n), không thể bé hơn. Trường hợp ta muốn Space Complexity là O(1) và Time Complexity: O(n)

Lúc này, Partitioning Arrays là một giải pháp đáng để xem xét. Partitioning (phân vùng), dựa trên ý tưởng này ta chia Array thành các phân vùng khác nhau.

Để thực hiện chia vùng trên Array, ta sẽ cần một giá trị, tạm đặt là boundary. Boundary sẽ chịu trách nhiệm chia Array thành 2 phần.

if (a[i] == 0):
    put a[i] to cloud partition

Mỗi lần phát hiện a[i] == 0, đồng thời ta cũng cập nhật boundary = boundary + 1. Tiếp tục loop trên i. Nhưng nếu chỉ put 0 vào cloud partition thì chưa đỏ. Cần phải đổi chỗ của phần tử i hiện tại với boundary

if (a[i] == 0):
    swap(i, boundary)
    boundary += 1

Implement cho bài toán này:

package com.src;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[]{7, 0, 3, 0, 6, 0};
        for (int item : moveZeroToFront(a)) {
            System.out.println(item);
        }
    }

    public static int[] moveZeroToFront(int[] a) {
        int boundary = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) {
                swap(a, i, boundary);
                boundary += 1;
            }
        }
        return a;
    }

    private static void swap(int a[], int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }
}

2. Mở rộng cho Partitioning Arrays

Một dạng khác khi làm việc với kỹ thuật Partitioning Arrays là Dutch National Flag Problem. Chia array thành 3 phần theo màu cờ Hà Lan. Cũng có khối ông trên thế giới cờ có 3 màu, nhưng thôi kệ.

Với một pivot cho trước, chia Array thành 3 vùng, phía trước nhỏ hơn pivot, bằng pivot và lớn hơn pivot.

If A = [5,2,4,4,6,4,4,3] and pivot = 4 -> result = [3,2,4,4,4,4,6,5]

Bài toán này yêu cầu tới 3 partitions, nên sẽ có 2 cloud được sử dụng.

Boundary lúc này chia thành low-boundary và high-boundary

if (a[i] < pivot):
    swap(i, low-boundary)
    low-boundary += 1

if (a[i] > pivot):
    swap(i, high-boundary)
    high-boundary -= 1

package com.src;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[]{3, 2, 1, 4, 0, 6, 7, 5};
        int pivot = 4;
        for (int item : dutchFlagSolve(a, pivot)) {
            System.out.println(item);
        }
    }

    public static int[] dutchFlagSolve(int[] a, int pivot) {
        int i = 0;
        int lowBoundary = 0;
        int highBoundary = a.length - 1;
        while (i <= highBoundary) {
            if (a[i] < pivot) {
                swap(a, i, lowBoundary);
                lowBoundary++;
                i++;
            } else if (a[i] > lowBoundary) {
                swap(a, i, highBoundary);
                highBoundary--;
            } else {
                i++;
            }
        }
        return a;
    }

    private static void swap(int a[], int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }
}

3. Tham khảo

• Partitioning values in an array – P-nand-Q
• Solve Reverse Array with the best solution
• Three way partitioning of an array around a given range

Thank you for your effort – Have a nice day – Happy coding!