Java 中排列二进制网格的最小交换次数

2025 年 1 月 6 日 | 阅读 16 分钟

通过交换行来以最少的交换次数排列二进制网格是一个令人兴奋的问题，它需要将给定的二进制网格转换为特定的形式。目标是确保网格中的每一行 i 至少有 n-1-i 个尾随零，其中 n 是网格的总行数。这个问题可以通过贪心算法、BFS 和线段树有效地解决。

Minimum Swaps to Arrange a Binary Grid in Java

示例

输入

A [] [] = [0 0 1]
              [1 1 0]
              [1 0 0]

输出

解释

对于第 0 行，它需要至少 2 个尾随零。有 2 个尾随零的行位于索引 2 处。我们用两次交换将它交换到索引 0。对于第 1 行，它需要至少 1 个尾随零。现在有 1 个尾随零的行位于索引 2 处。我们用一次交换将其交换到索引 1。对于第 2 行，它需要至少 0 个尾随零，而它已经有了，所以不需要交换。总交换次数为 3。

方法 1：BFS (广度优先搜索)

广度优先搜索 (BFS) 方法将问题视为状态空间搜索，其中每个状态代表网格的一种配置，我们的目标是找到最短路径（最少交换次数）。它通过交换行来探索网格的所有可能配置，并使用队列来跟踪要探索的配置。

算法

步骤 1：创建一个 trailingZeros 数组来存储每行尾随零的数量。使用队列来存储网格的配置。使用集合来跟踪已访问的配置，以避免冗余处理。

步骤 2：计算尾随零：遍历网格的每一行，并计算尾随零的数量。将这些计数存储在 trailingZeros 数组中。

步骤 3：BFS 设置：将初始的 trailingZeros 配置入队，并将其标记为已访问。初始化一个变量 swaps 来计算所需的交换次数。

步骤 4：BFS 循环：出队一个配置。检查当前配置是否有效。如果有效，则返回达到该配置所需的交换次数。

步骤 5：通过交换相邻行来生成所有可能的配置。如果新配置未被访问过，则将其入队并标记为已访问。

步骤 6：如果队列耗尽而未找到有效配置，则返回 -1。

文件名：MinimumSwapsBinaryGridBFS.java

import java.util.*;
public class MinimumSwapsBinaryGridBFS {
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        // Calculate the number of trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }
        // Use a queue for BFS
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.add(trailingZeros.clone());
        visited.add(Arrays.toString(trailingZeros));
        int swaps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] current = queue.poll();
                // Check if the current configuration is valid
                boolean valid = true;
                for (int i = 0; i < n; i++) {
                    if (current[i] < n - 1 - i) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    return swaps;
                }
                // Generate all possible configurations by swapping adjacent rows
                for (int i = 0; i < n - 1; i++) {
                    int[] next = current.clone();
                    int temp = next[i];
                    next[i] = next[i + 1];
                    next[i + 1] = temp;
                    String key = Arrays.toString(next);
                    if (!visited.contains(key)) {
                        queue.add(next);
                        visited.add(key);
                    }
                }
            }
            swaps++;
        }
        // If the queue is exhausted, return -1
        return -1;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid)); // Output: 3
    }
}

输出

时间复杂度

在最坏的情况下，BFS 可能需要探索行的所有可能排列，即 n!。对于每次排列，检查有效性需要 O(n)，生成新配置需要 O(n⋅n)=O(n²)。因此，BFS 探索的总时间复杂度为 O((n!)* n²)。

空间复杂度

队列最多可以包含 n! 个配置，每个配置的大小为 n。已访问集合也存储最多 n! 个配置，每个配置的大小为 n。因此，空间复杂度为 O((n!)* n)。

方法 2：使用线段树

在此问题中，我们可以使用线段树来管理网格中每行尾随零的数量，从而使我们能够快速确定排列网格所需的最小交换次数。

算法

步骤 1：创建一个大小为 n 的 trailingZeros 数组，用于存储每行尾随零的计数。

步骤 2：计算尾随零：从 0 到 n-1 遍历每一行 i。对于每一行，从右到左（从 n-1 到 0）遍历其元素。计算行末尾连续零的数量，并将此计数存储在 trailingZeros[i] 中。

步骤 3：构建线段树线段树构造：初始化一个线段树，其中每个叶节点对应于尾随零的计数。使用 trailingZeros 数组构建线段树。

步骤 4：范围查询：对于每一行 i，确定所需的尾随零数量 (n - 1 - i)。使用线段树执行范围最小查询，以查找 i 到数组末尾范围内的最小尾随零。

步骤 5：如果找到的最小值小于所需的零，则找到相应的行索引。

步骤 6：交换行，将具有所需尾随零的行移动到正确的位置。交换后更新线段树以反映新的尾随零计数。

文件名：MinimumSwapsBinaryGridST.java

public class MinimumSwapsBinaryGridST {
    static class SegmentTree {
        int[] tree;
        int n;
        SegmentTree(int size) {
            n = size;
            tree = new int[2 * n];
        }
        void build(int[] arr) {
            for (int i = 0; i < n; i++) {
                tree[n + i] = arr[i];
            }
            for (int i = n - 1; i > 0; --i) {
                tree[i] = Math.min(tree[i * 2], tree[i * 2 + 1]);
            }
        }
        void update(int p, int value) {
            p += n;
            tree[p] = value;
            for (int i = p / 2; i > 0; i /= 2) {
                tree[i] = Math.min(tree[i * 2], tree[i * 2 + 1]);
            }
        }
        int query(int l, int r) {
            l += n;
            r += n;
            int res = Integer.MAX_VALUE;
            while (l < r) {
                if ((l & 1) == 1) res = Math.min(res, tree[l++]);
                if ((r & 1) == 1) res = Math.min(res, tree[--r]);
                l /= 2;
                r /= 2;
            }
            return res;
        }
    }
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        // Calculate the number of trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }
        // Build the segment tree
        SegmentTree segTree = new SegmentTree(n);
        segTree.build(trailingZeros);
        int swaps = 0;
        // Iterate over each row to place it in the correct position
        for (int i = 0; i < n; i++) {
            int requiredZeros = n - 1 - i;
            // Perform a range minimum query to find the minimum trailing zeros
            int rowIndex = -1;
            for (int j = i; j < n; j++) {
                if (trailingZeros[j] >= requiredZeros) {
                    rowIndex = j;
                    break;
                }
            }
            if (rowIndex == -1) {
                return -1; // No valid row found
            }
            // Perform swaps to move the row to the correct position
            for (int j = rowIndex; j > i; j--) {
                int temp = trailingZeros[j];
                trailingZeros[j] = trailingZeros[j - 1];
                trailingZeros[j - 1] = temp;
                swaps++;
            }
            // Update the segment tree after each swap
            segTree.update(i, trailingZeros[i]);
            for (int j = i + 1; j <= rowIndex; j++) {
                segTree.update(j, trailingZeros[j]);
            }
        }
        // Return the total number of swaps
        return swaps;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid)); 
    }
}

输出

时间复杂度

我们遍历网格的每个元素来计算尾随零，这需要 O(n²)。线段树的每个查询和更新操作需要 O(logn)，我们执行这些操作 n 次，因此是 O(nlogn)。因此，总时间复杂度为 O(n²+ nlogn)。

空间复杂度

尾随零数组的空间为 O(n)：我们使用一个 trailingZeros 数组来存储每行尾随零的计数。因此，空间复杂度为 O(n)。

方法 3：Fenwick 树 (二叉索引树)

在排列二进制网格并以最少交换次数进行处理的上下文中，可以使用 Fenwick 树来有效地跟踪具有足够尾随零的行的位置，这使我们能够快速确定将行移到正确位置所需的最小交换次数。

算法

步骤 1：初始化变量：n、trailingZeros 和 FenwickTree：一个数据结构，用于跟踪计数并执行有效的预缀和查询和更新。

步骤 2：对于每一行，从右到左计算尾随零（0）的数量。将计数存储在 trailingZeros 数组中。

步骤 3：创建一个大小为 n 的 Fenwick 树。使用每行尾随零的计数来更新树。

步骤 4：对于从 0 到 n-1 的每个位置 i：计算要放在位置 i 的行所需的尾随零数量（即 n - 1 - i）。

步骤 5：使用 Fenwick 树查找具有足够尾随零的最近行。如果找不到这样的行，则返回 -1（表示无法排列网格）。

步骤 6：对于找到的每一行，执行必要的交换以将该行移到正确的位置。

步骤 7：每次交换后更新 Fenwick 树以反映 trailingZeros 数组的当前状态。返回排列网格所需的总交换次数。

文件名：MinimumSwapsBinaryGridFT.java

public class MinimumSwapsBinaryGridFT {
    static class FenwickTree {
        private int[] tree;
        public FenwickTree(int size) {
            tree = new int[size + 1];
        }
        public void update(int index, int delta) {
            while (index < tree.length) {
                tree[index] += delta;
                index += index & -index;
            }
        }
        public int query(int index) {
            int sum = 0;
            while (index > 0) {
                sum += tree[index];
                index -= index & -index;
            }
            return sum;
        }
        public int queryRange(int left, int right) {
            return query(right) - query(left - 1);
        }
    }
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        // Calculate the number of trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }
        // Initialize the Fenwick Tree
        FenwickTree fenwickTree = new FenwickTree(n);
        for (int i = 0; i < n; i++) {
            fenwickTree.update(i + 1, trailingZeros[i]);
        }
        int swaps = 0;
        // Iterate over each row to place it in the correct position
        for (int i = 0; i < n; i++) {
            int requiredZeros = n - 1 - i;
            int rowIndex = -1;
            for (int j = i; j < n; j++) {
                if (trailingZeros[j] >= requiredZeros) {
                    rowIndex = j;
                    break;
                }
            }
            if (rowIndex == -1) {
                return -1; // No valid row found
            }
            // Perform swaps to move the row to the correct position
            for (int j = rowIndex; j > i; j--) {
                int temp = trailingZeros[j];
                trailingZeros[j] = trailingZeros[j - 1];
                trailingZeros[j - 1] = temp;
                swaps++;
            }
            // Update the Fenwick Tree after each swap
            fenwickTree.update(i + 1, trailingZeros[i]);
            for (int j = i + 1; j <= rowIndex; j++) {
                fenwickTree.update(j + 1, trailingZeros[j]);
            }
        }
        // Return the total number of swaps
        return swaps;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid));
    }
}

输出

时间复杂度

计算尾随零：O(n²) 遍历网格的每个元素。Fenwick 树操作：O(nlogn) 用于更新和查询。总时间复杂度：O(n²+ nlogn)。

空间复杂度

尾随零数组的空间复杂度为 O(n)：我们存储 n 行中每一行的尾随零的数量。Fenwick 树也需要 O(n) 空间：其大小与行数成正比。因此，总空间复杂度为 O(n)。

方法 4：使用尾随零的贪心方法

以使每行 i 至少有 n-1-i 个尾随零的方式排列二进制网格的问题，可以使用贪心方法有效地解决。这种方法涉及计算每行尾随零的数量，并进行最少的交换以满足每一行的条件。

算法

步骤 1：创建一个 trailingZeros 数组来存储每行尾随零的数量。初始化一个变量 swaps 来计算所需的交换次数。

步骤 2：遍历网格的每一行。对于每一行，通过从最后一个元素到第一个元素进行迭代来计算尾随零的数量。将尾随零的数量存储在 trailingZeros 数组中。

步骤 3：贪心行放置：对于每一行 i（从第一行到最后一行）：计算当前行所需的尾随零数量，即 n-1-i。

步骤 4：检查当前行 i 是否具有所需的尾随零数量。如果没有，则查找下方满足要求的合适行。

步骤 5：如果没有找到合适的行，则返回 -1，表示无法排列网格。如果找到了合适的行，则将其向上交换到当前位置 i，并计算所需的交换次数。

步骤 6：处理完所有行后，返回用于排列网格的总交换次数。

文件名：MinimumSwapsBinaryGrid.java

public class MinimumSwapsBinaryGrid {
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        // Calculate the number of trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }
        int swaps = 0;
        // Greedy row placement
        for (int i = 0; i < n; i++) {
            int requiredZeros = n - 1 - i;
            int rowIndex = i;
            // Find the row that can be moved to the i-th position
            while (rowIndex < n && trailingZeros[rowIndex] < requiredZeros) {
                rowIndex++;
            }
            // If no such row is found, it is impossible to arrange the grid
            if (rowIndex == n) {
                return -1;
            }
            // Move the found row to the correct position by swapping
            while (rowIndex > i) {
                int temp = trailingZeros[rowIndex];
                trailingZeros[rowIndex] = trailingZeros[rowIndex - 1];
                trailingZeros[rowIndex - 1] = temp;
                rowIndex--;
                swaps++;
            }
        }
        // Return the total number of swaps
        return swaps;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid)); 
    }
}

输出

时间复杂度

我们遍历每行（大小为 n），并且对于每行，我们遍历其元素（大小为 n）。因此，嵌套循环导致 O(n²) 时间复杂度。

空间复杂度

我们为大小为 n 的 trailingZeros 数组使用额外的空间来存储每行尾随零的数量。除此之外，我们使用一些常数额外的变量用于索引和计数器。因此，空间复杂度为 O(n)。

方法 5：优化计数排序

优化的计数排序方法利用计数和排序技术来有效地确定排列行所需的最小交换次数。通过跟踪每行尾随零的数量并使用计数排序原理，我们可以以最小的计算开销确定行的正确位置。

算法

步骤 1：创建一个大小为 n 的 trailingZeros 数组，用于存储每行尾随零的计数。从 0 到 n-1 遍历每一行 i。计算行末尾连续零的数量，并将此计数存储在 trailingZeros[i] 中。

步骤 2：创建一个计数数组，以有效地查找可以移到当前位置的行。从 0 到 n-1 遍历每一行 i。确定第 i 行所需的尾随零数量，即 n - 1 - i。

步骤 3：通过递增 rowIndex 直到找到合适的行或达到网格末尾，从当前位置查找最近的满足此要求的行。

步骤 4：交换行：如果找到合适的行 (rowIndex < n)，则交换行将合适的行移到位置 i。

步骤 5：使用 while 循环执行交换，直到 rowIndex 等于 i，并为执行的每次交换递增交换计数。

步骤 6：处理完所有行后，返回为实现所需排列执行的总交换次数。

文件名：MinimumSwapsBinaryGridOCS.java

public class MinimumSwapsBinaryGridOCS {
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        // Calculate the number of trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }
        int swaps = 0;
        // Iterate over each row to place it in the correct position
        for (int i = 0; i < n; i++) {
            int requiredZeros = n - 1 - i;
            int rowIndex = i;
            // Find the row that can be moved to the i-th position
            while (rowIndex < n && trailingZeros[rowIndex] < requiredZeros) {
                rowIndex++;
            }
            // If no such row is found, it is impossible to arrange the grid
            if (rowIndex == n) {
                return -1;
            }
            // Move the found row to the correct position by swapping
            while (rowIndex > i) {
                int temp = trailingZeros[rowIndex];
                trailingZeros[rowIndex] = trailingZeros[rowIndex - 1];
                trailingZeros[rowIndex - 1] = temp;
                rowIndex--;
                swaps++;
            }
        }
        // Return the total number of swaps
        return swaps;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid)); 
    }
}

输出

时间复杂度

我们遍历网格的每个元素来计算尾随零，这需要 O(n^2)。对于每一行，在最坏的情况下，我们可能需要将其与下方的每一行进行交换，这需要 O(n) 次操作。因此，总时间复杂度为 O(n²)。

空间复杂度

尾随零数组的空间复杂度：O(n)，我们使用一个 trailingZeros 数组来存储每行尾随零的计数。因此，总空间复杂度为 O(n)。

方法 6：使用最后一个“1”位置的贪心方法

贪心方法包括识别每行最后一个“1”的位置，然后重新排列行，使得每行 i 满足最后一个“1”在该行位于位置 i 或更早的位置的条件。

算法

步骤 1：初始化位置数组：创建一个 pos 数组，其中 pos[i] 存储行 i 中最后一个“1”的位置。如果一行没有“1”，则其位置设置为 -1。

步骤 2：计算最后一个“1”的位置：遍历网格的每一行，并确定最后一个“1”的位置。将这些位置存储在 pos 数组中。

步骤 3：贪心行放置：从 0 到 n-1 遍历每一行 i，并确保位置 i 的行满足最后一个“1”在位置 i 或更早位置的条件。

步骤 4：如果当前行 i 不满足条件，则查找下方 i 附近满足条件的行，并根据需要交换行。

步骤 5：执行交换：将当前行与上一步找到的合适行交换，并为执行的每次交换递增交换计数。

步骤 6：检查有效配置：如果找不到合适的行，则返回 -1，表示无法排列网格。返回为实现所需排列执行的总交换次数。

文件名：MinimumSwapsBinaryGrid1.java

public class MinimumSwapsBinaryGrid1 {
    public static int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] pos = new int[n];
        // Find the position of the last '1' in each row
        for (int i = 0; i < n; i++) {
            pos[i] = -1; // Initialize with -1 to handle rows with no '1'
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }
        }
        int swaps = 0;
        // Iterate over each row to place it in the correct position
        for (int i = 0; i < n; i++) {
            int target = i;
            // Find the row that can be moved to the i-th position
            while (target < n && pos[target] > i) {
                target++;
            }
            // If no such row is found, it is impossible to arrange the grid
            if (target == n) {
                return -1;
            }
            // Move the found row to the correct position by swapping
            while (target > i) {
                int temp = pos[target];
                pos[target] = pos[target - 1];
                pos[target - 1] = temp;
                target--;
                swaps++;
            }
        }
        // Return the total number of swaps
        return swaps;
    }
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 1},
            {1, 1, 0},
            {1, 0, 0}
        };
        System.out.println(minSwaps(grid)); // Output: 3
    }
}

输出

时间复杂度

我们遍历网格的每个元素来查找每行最后一个“1”的位置，这需要 n×n=n^2 次操作。在最坏的情况下，对于每一行，我们可能需要将其与下方的每一行进行交换，这需要 O(n) 次操作。因此，总复杂度为 O(n²)。

空间复杂度

空间复杂度为 O(n)：使用的额外空间主要是 pos 数组，该数组存储 n 行中每一行最后一个“1”的位置。

下一个主题Array-partition-problem-in-java

Java 中排列二进制网格的最小交换次数

方法 1：BFS (广度优先搜索)

算法

方法 2：使用线段树

算法

方法 3：Fenwick 树 (二叉索引树)

算法

方法 4：使用尾随零的贪心方法

算法

方法 5：优化计数排序

算法

方法 6：使用最后一个“1”位置的贪心方法

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中排列二进制网格的最小交换次数

方法 1：BFS (广度优先搜索)

算法

方法 2：使用线段树

算法

方法 3：Fenwick 树 (二叉索引树)

算法

方法 4：使用尾随零的贪心方法

算法

方法 5：优化计数排序

算法

方法 6：使用最后一个“1”位置的贪心方法

算法

相关帖子

Java 中的预定义流

ChocolatesByNumbers Problem in Java

What is Object-Oriented Programming?

Java 中的 ConcurrentSkipListSet

Java 程序演示非懒惰初始化线程安全

Java 中的字典类

Java 中显示整数数组的所有子集

Java 中作为参数的对象

How to Achieve Performance in Multithreading in Java?

Java 中的 Brilliant 数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器