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;
    }
}