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
Example 2:
Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] Output: -1 Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,1]] Output: 0
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j]
is0
or1
Solution: Bubble Sort
Counting how many tailing zeros each row has.
Then input
[0, 0, 1]
[1, 1, 0]
[1, 0, 0]
becomes [0, 1, 2]
For i-th row, it needs n – i – 1 tailing zeros.
We need to find the first row that has at least n – i – 1 tailing zeros and bubbling it up to the i-th row. This process is very similar to bubble sort.
[0, 1, 2] -> [0, 2, 1] -> [2, 0, 1]
[2, 0, 1] -> [2, 1, 0]
Total 3 swaps.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public: int minSwaps(vector<vector<int>>& grid) { const int n = grid.size(); vector<int> zeros; for (const auto& row : grid) { int zero = 0; for (int i = n - 1; i >= 0 && row[i] == 0; --i) ++zero; zeros.push_back(zero); } int ans = 0; for (int i = 0; i < n; ++i) { int j = i; int z = n - i - 1; // the i-th needs n - i - 1 zeros // Find first row with at least z tailing zeros. while (j < n && zeros[j] < z) ++j; if (j == n) return -1; while (j > i) { zeros[j] = zeros[j - 1]; --j; ++ans; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment