Minimum Swaps to Arrange a Binary Grid

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

 

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

思路:这是greedy的题目，首先收集每一行，从右往左看有多少个0的个数，然后用greedy的思想，每一行，期待的0的个数是知道的，比如第一行，我期待 n - 1个0，所以如果第一行不满足，我就去找下面第一个遇见满足我的条件的0的row j,把 row  j往上swap，swap多少次，就记录多少次，然后每一行每一行的这么进行就是greedy。

class Solution {
    public int minSwaps(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int n = grid.length;
        // 收集从右边往左看，row的0的个数；
        int[] arr = getZeroCount(grid);
        int step = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] < n - i - 1) {
                int j = i;
                // greedy的思想：找到满足第i行所需要0的个数的第一个row的index j, 然后把j往上移动；
                while(j < n && arr[j] < n - i - 1) {
                    j++;
                }
                if(j == n) {
                    return -1;
                }
                while(j > i) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    j--;
                    step++; // swap多少次，就记录step多少次；
                }
            }
        }
        return step;
    }
    
    private int[] getZeroCount(int[][] grid) {
        int n = grid.length;
        int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            int count = 0;
            int j = n - 1;
            while(j >= 0 && grid[i][j] == 0) {
                count++;
                j--;
            }
            res[i] = count;
        }
        return res;
    }
}