LeetCode之排布二进制网格的最少交换次数（一千五百三十六）

目录

题目

解题

方法一、类比法

题目

（原题链接：https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid/）

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

示例 1：

示例 2：

示例 3：

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 200
• grid[i][j] 要么是 0 要么是 1 。

解题

方法一、类比法

分析：该题仔细分析后，其实类比成排序问题，求解排序完成需要移动的次数。

代码：（C++）

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 int minSwaps(vector<vector<int>>& grid) {
     
    
   

    

     

    
    

     
 int n = grid.size(); //网格规模
     
    
   

    

     

    
    

     
 vector<int> a; //记录每一行后缀0的个数
     
    
   

    

     

    
    

     
 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;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       a.push_back(count); 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int count = 0; //交换次数
     
    
   

    

     

    
    

     
 for (int i = 0; i < n - 1; i++) {
     
    
   

    

     

    
    

     
 if (a[i] >= n - i - 1) {
     
    
   

    

     

    
    

     
 continue;//满足条件，该行直接跳过
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     
 else {//不满足条件
     
    
   

    

     

    
    

     
 int j = i; //遍历满足条件的后缀0
     
    
   

    

     

    
    

     
 for (; j < n; j++) {
     
    
   

    

     

    
    

     
 if (a[j] >= n - i - 1) {
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (j == n) {
     
    
   

    

     

    
    

     
 return -1; //找不到，直接返回-1
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for (; j > i; j--) {
     
    
   

    

     

    
    

     

       swap(a[j], a[j - 1]); //每一行交换上去
     
    
   

    

     

    
    

     

       count++; //记录交换次数
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return count;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n*m）。

空间复杂度：O（n）。

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107803817