Segregate 0s and 1s Problem in Java

2025年5月6日 | 阅读4分钟

这是Google、Amazon、TCS、Accenture、Flipkart 等顶级 IT 公司面试中经常提出的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的技巧。因此，在本节中，我们将通过不同的方法和逻辑来解决分离 0 和 1 的问题。我们还将为此创建 Java 程序。

分离 0 和 1 的问题 简单地重新排列 0 和 1 的数组，使所有 0 出现在一侧（通常是左侧），所有 1 出现在另一侧。这个问题通常被认为是双指针技术的一种形式，并且是数组操作的基本问题。

这个问题对于理解基本的排序技术、处理数组中有限值以及实现具有最小时间复杂度的就地算法至关重要。

示例

输入数组 {0, 1, 1, 0, 1, 0, 0, 1, 1, 0}

初始状态

left = 0, right = 9（开始和结束索引）
数组：{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}

第一次迭代

arr[left] = 0（已正确，left 增加到 1）。
arr[right] = 0（与 arr[left] 交换）。
交换后的数组：{0, 0, 1, 0, 1, 0, 0, 1, 1, 1}

第二次迭代

left = 2, right = 8。
arr[left] = 1, arr[right] = 1（right 减少到 7）。

第三次迭代

left = 2, right = 7。
arr[left] = 1, arr[right] = 0（交换）。
交换后的数组：{0, 0, 0, 0, 1, 1, 1, 1, 1, 1}

End

指针在索引 5 处相遇；循环结束。
最终数组：{0, 0, 0, 0, 1, 1, 1, 1, 1, 1}

解决问题的方法

朴素方法（计数）
- 计算数组中的 0 和 1 的数量。
- 通过先放置所有 0，然后放置所有 1 来覆盖数组。
- 时间复杂度：（O(n)）
- 空间复杂度：（O(1)）
高效方法（双指针技术）
- 使用两个指针。一个从左侧开始，另一个从右侧开始。
- 移动左指针，直到找到一个 1。
- 移动右指针，直到找到一个 0。
- 交换这些指针处的元素，并继续直到指针相遇。
- 时间复杂度：（O(n)）
- 空间复杂度：（O(1)）

文件名：SegregateZerosAndOnes.java

public class SegregateZerosAndOnes {
    // Method to segregate 0s and 1s using twopointer technique
    public static void segregateZerosAndOnes(int[] arr) {
        int left = 0, right = arr.length  1;
        while (left < right) {
            // Increment left pointer if current element is 0
            if (arr[left] == 0) {
                left++;
            }
            // Decrement right pointer if current element is 1
            else if (arr[right] == 1) {
                right;
            }
            // Swap if left is 1 and right is 0
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                // Move pointers inward
                left++;
                right;
            }
        }
    }
    // Utility function to print the array
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    // Main method
    public static void main(String[] args) {
        // Sample input array
        int[] arr = {0, 1, 1, 0, 1, 0, 0, 1, 1, 0};
        System.out.println("Original Array:");
        printArray(arr);
        // Perform segregation
        segregateZerosAndOnes(arr);
        System.out.println("Array after segregation:");
        printArray(arr);
    }
}   

输出

 
Original Array:
0 1 1 0 1 0 0 1 1 0 
Array after segregation:
0 0 0 0 0 1 1 1 1 1

解释

给定的 Java 程序使用双指针技术分离数组中的 0 和 1，确保了一种高效且就地（in-place）的解决方案。它初始化两个指针，left 指针指向数组的开头，right 指针指向数组的末尾。

left 指针向前移动，寻找 0，因为它们已处于正确的位置；right 指针向后移动，寻找 1。当 arr[left] 是 1 且 arr[right] 是 0 时，两个值都会被交换到正确的位置，并且两个指针都会向内移动。

此过程将一直持续到指针相遇，最终结果是所有 0 在左边，所有 1 在右边。这种方法保证了时间复杂度为 O(n)（这里原文写的是 O(1)，但实际是 O(n)），空间复杂度为 O(1)，使其对于二元数组非常高效。

双指针技术的优点

时间效率高
数组只遍历一次，使算法的时间复杂度为 O(n)。
空间效率高
该技术使用恒定的额外空间（O(1)），因为所有操作都是就地完成的。
简单性
逻辑简单，避免了额外数据结构的开销。

用例

二进制排序： 在网络和硬件应用中重新排列二进制数组。
预处理： 在应用高级算法（如搜索或索引）之前，分离数据可以简化逻辑。
其他分离问题： 可以将其改编为根据其他标准对数组进行分区（例如，负数和正数）。

复杂度分析

1. 时间复杂度

该算法对数组进行一次遍历，对每个元素进行常数时间的比较和交换。

最佳情况： O(n)（已排序，无需交换）。
最坏情况： O(n)（需要最大次数的交换，但仍是线性遍历）。
平均情况： O(n)（无论输入顺序如何，都是线性遍历）。

2. 空间复杂度

该算法完全在原地操作，不需要额外的内存。

辅助空间： O(1)，因为它只使用两个指针和一个临时变量进行交换。

3. 优化效率

恒定的空间复杂度和线性时间复杂度使得该算法非常高效，尤其是在处理大型数组时。它避免了使用额外数据结构的开销，在内存受限的系统中提供了性能优势。

结论

“分离 0 和 1”问题通过双指针技术演示了就地排序的力量。它有效地重新排列二进制数组，而无需额外的空间，确保所有 0 都位于左侧，所有 1 都位于右侧。

该方法简单而最优，适合初学者和高级程序员。通过最小化遍历和交换次数，它强调了优化算法时间复杂度和空间复杂度的重要性，尤其是在处理大型数据集时。

该解决方案非常健壮，可以作为解决更复杂的分离问题的基础。

下一主题Kruskal 算法 Java

Segregate 0s and 1s Problem in Java

示例

解决问题的方法

解释

双指针技术的优点

用例