LeetCode题解-数组与矩阵

冷不防 2022-11-18 02:00 742阅读 0赞

## LeetCode题解-数组与矩阵 ##

### 文章目录 ###

*   *  LeetCode题解-数组与矩阵
     *   *  283.移动零（简单）
         *  566.重塑矩阵（简单）
         *  59.螺旋矩阵 ll（中等）
         *  54.螺旋矩阵（中等）
         *  74. 搜索二维矩阵（中等）
         *  240.搜索二维矩阵 ll（中等）
         *  378.有序矩阵中第k小的元素（中等）
         *  剑指offer 03.数组中重复的数字（简单）
         *  645.错误的集合（简单）
         *   *   *  复杂度分析：
         *  287.寻找重复数（中等）
         *  697.数组的度（简单）
         *  766.托普利茨矩阵（简单）
         *  565.数组嵌套（中等）
         *  769.最多能完成排序的块（中等）

--------------------

### 283.移动零（简单） ###

给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

1.  必须在原数组上操作，不能拷贝额外的数组。
2.  尽量减少操作次数。

**解题思路**：双指针——两个指针初始位于数组开头，  i i i 指针用来遍历数组，  j j j 指针用来记录下一个需要交换的位置，当  i i i 指针遍历到的数字不为0时，则将两个指针的数据交换位置，同时  j j j 指针向右挪动一位。

class Solution {
        
        public void moveZeroes(int[] nums) {
        
            if(nums == null || nums.length == 0){
        
                return;
            }
            int j = 0;
            for(int i = 0; i < nums.length; i++){
        
                if(nums[i] != 0){
        
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    j++;
                }
            }
        }
    }

--------------------

### 566.重塑矩阵（简单） ###

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

输入: 
    nums = 
    [[1,2],
     [3,4]]
    r = 1, c = 4
    输出: 
    [[1,2,3,4]]
    解释:
    行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

**解题思路**：找出矩阵中每个元素的行、列索引与整体元素个数之间的关系

*  设nums本身为 m 行 n 列，如果 mn≠rc，那么二者包含的元素个数不相同，因此无法进行重塑；
 *  否则，对于 x∈\[0,mn)，第 x 个元素在nums 中对应的下标为 (x / n,x % n)，而在新的重塑矩阵中对应的下标为 (x / c,x % c)，直接进行赋值即可。

class Solution {
        
        public int[][] matrixReshape(int[][] nums, int r, int c) {
        
            int m = nums.length, n = nums[0].length;//二维数组行列的大小取值也要记一下
            if(m * n != r * c){
        
                return nums;
            }
            int[][] reshapeMatrix = new int[r][c];
            for(int i = 0; i < m * n; i ++){
        
                reshapeMatrix[i / c][i % c] = nums[i / n][i % n];
            }
            return reshapeMatrix;
        }
    }

--------------------

### 59.螺旋矩阵 ll（中等） ###

给你一个正整数 `n` ，生成一个包含 `1` 到 `n^2` 所有元素，且元素按顺时针顺序螺旋排列的 `n x n` 正方形矩阵 `matrix` 。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hSRgN3BU-1618151363176)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210322211014900.png)\]][img-hSRgN3BU-1618151363176_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210322211014900.png]

输入：n = 3
    输出：[[1,2,3],[8,9,4],[7,6,5]]

**解题思路**

*  生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程：
    
     *  定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 sum = n \* n；
     *  当 num <= tar 时，始终按照 从左到右、 从上到下、 从右到左、 从下到上填入顺序循环，每次填入后：
        
        1.  执行 num += 1：得到下一个需要填入的数字；
        2.  更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
 *  使用num <= sum而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JH7JKHMZ-1618151363178)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210322211504269.png)\]][img-JH7JKHMZ-1618151363178_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210322211504269.png]

class Solution {
        
        public int[][] generateMatrix(int n) {
        
            int l = 0, r = n - 1, t = 0, b = n - 1;
            int[][] res = new int[n][n];
            int num = 1, sum = n * n;
            while(num <= sum){
        
                for(int i = l; i <= r; i++) res[t][i] = num++; //从左到右
                t++; //上边界加1
                for(int i = t; i <= b; i++) res[i][r] = num++; //从上到下
                r--; //右边界减1
                for(int i = r; i >= l; i--) res[b][i] = num++; //从右到左
                b--; //下边界减1
                for(int i = b; i >= t; i--) res[i][l] = num++; //从下到上
                l++; //左边界加1
            }
            return res;
        }
    }

--------------------

### 54.螺旋矩阵（中等） ###

给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素。（如上题图示）

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]

**解题思路**：与上题类似，按照 从左到右、 从上到下、 从右到左、 从下到上的顺序遍历整个矩阵，并依次填入列表中，需要注意的是，该题的矩阵有可能是长方形，所以需要再加一个约束条件。

class Solution {
        
        public List<Integer> spiralOrder(int[][] matrix) {
        
           List<Integer> res = new ArrayList<>();
           int m = matrix.length, n = matrix[0].length;
           int l = 0, r = n - 1, t = 0, b = m - 1;
           int num = 1;
           while(num <= m*n){
        
               for(int i = l; i <= r && num <= m*n; i++){
         //注意这个新的约束条件，否则会多输出元素
                   res.add(matrix[t][i]);
                   num++;
               }
               t++;
               for(int i = t; i <= b && num <= m*n; i++){
        
                   res.add(matrix[i][r]);
                   num++;
               } 
               r--;
               for(int i = r; i >= l && num <= m*n; i--){
        
                   res.add(matrix[b][i]);
                   num++;
               }
               b--;
               for(int i = b; i >= t && num <= m*n; i--){
        
                   res.add(matrix[i][l]);
                   num++;
               }
               l++;
           }
            return res;
        }
    }

### 74. 搜索二维矩阵（中等） ###

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eR73yHsM-1618151363179)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210323202702150.png)\]][img-eR73yHsM-1618151363179_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323202702150.png]

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
    输出：true

**解题思路：**

方法一：左下角搜索：找到边角元素，该元素走一个方向减小，走另一个方向增大（思路类似于二叉搜索树）

*  左下角的元素是这一行中最小的元素，同时又是这一列中最大的元素。比较左下角元素和目标：
    
     *  若左下角元素等于目标，则找到
     *  若左下角元素大于目标，则目标不可能存在于当前矩阵的最后一行，问题规模可以减小为在去掉最后一行的子矩阵中寻找目标
     *  若左下角元素小于目标，则目标不可能存在于当前矩阵的第一列，问题规模可以减小为在去掉第一列的子矩阵中寻找目标
 *  若最后矩阵减小为空，则说明不存在

class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
            int m = matrix.length, n = matrix[0].length;
            if(matrix == null || m == 0 || n == 0) return false;
            int i = m-1, j = 0;
            while(i >= 0 && j < n){
        
                if(matrix[i][j] > target) {
        
                    i --;
                }else if(matrix[i][j] < target){
        
                    j ++;
                }else{
        
                    return true;
                }
            }
            return false;
        }
    }

*  时间复杂度： O ( n + m ) O(n+m) O(n\+m)

--------------------

方法二：二分查找:输入的 `m x n` 矩阵可以视为长度为 `m x n`的有序数组

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aWFySPuS-1618151363180)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210323202830287.png)\]][img-aWFySPuS-1618151363180_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323202830287.png]

class Solution {
        
      public boolean searchMatrix(int[][] matrix, int target) {
        
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;
    
        // 二分查找
        int left = 0, right = m * n - 1;
        int pivotIdx, pivotElement;
        while (left <= right) {
         //注意此处必须是小于等于
          midIdx = (left + right) / 2; //找到中间索引
          midElement = matrix[midIdx / n][midIdx % n]; //注意这里的索引取值，需要记住，经常会用到！！！
          if (target == midElement) return true;
          else {
        
            if (target < midElement) right = midIdx - 1;
            else left = midIdx + 1;
          }
        }
        return false;
      }
    }

*  时间复杂度： O ( l o g ( n ∗ m ) ) O(log(n\*m)) O(log(n∗m))

--------------------

### 240.搜索二维矩阵 ll（中等） ###

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。每列的元素从上到下升序排列。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N5C1kr2v-1618151363181)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210323200156647.png)\]][img-N5C1kr2v-1618151363181_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323200156647.png]

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
    输出：true

\*\*解题思路：\*\*与上题的方法一思路相同，从左下角开始搜索

*  若左下角元素等于目标，则找到
 *  若左下角元素大于目标，则目标不可能存在于当前矩阵的最后一行，问题规模可以减小为在去掉最后一行的子矩阵中寻找目标
 *  若左下角元素小于目标，则目标不可能存在于当前矩阵的第一列，问题规模可以减小为在去掉第一列的子矩阵中寻找目标

class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
           if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
           int m = matrix.length, n = matrix[0].length;
           int row = m - 1, col = 0;
           while(row >= 0 && col < n){
        
               if(matrix[row][col] > target){
        
                   row--;
               }else if(matrix[row][col] < target){
        
                   col++;
               }else{
        
                   return true;
               }
           }
           return false; 
        }
    }

--------------------

### 378.有序矩阵中第k小的元素（中等） ###

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。  
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
    输出：13
    解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

**解题方法一：**直接排序\_\_将这个二维数组转成一维数组，并对该一维数组进行排序。最后这个一维数组中的第 k个数即为答案。

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
                   
            int m = matrix.length, n = matrix[0].length;
            int[] sortedMatrix = new int[m * n];
            int index = 0;
            for(int i = 0; i < m; i++){
        
                for(int j = 0; j < n; j++){
        
                    sortedMatrix[index++] = matrix[i][j];
                }
            }
            Arrays.sort(sortedMatrix);//记住这个函数
            return sortedMatrix[k - 1];
        }
    }

*  时间复杂度： O ( n 2 l o g n ) O(n^2logn) O(n2logn)：对 n 2 n^2 n2个数排序
 *  空间复杂度： O ( n 2 ) O(n^2) O(n2),一维数组需要存储这 n 2 n^2 n2个数

--------------------

**解题方法二**：二分查找

由题目给出的性质可知，整个二维数组中的元素是从左上到右下递增的，  m a t r i x \[ 0 \] \[ 0 \] matrix\[0\]\[0\] matrix\[0\]\[0\]为最小值，为 m a t r i x \[ m − 1 \] \[ n − 1 \] matrix\[m-1\]\[n-1\] matrix\[m−1\]\[n−1\]最大值，我们分别将它们记为 l e f t left left和 r i g h t right right，因此对**值域**进行二分查找，算出中间值 m i d mid mid，每次计算求出小于等于 m i d mid mid 的元素个数 c o u n t count count，当 $count < k $ 时，说明该元素在右半部分，则调整值域范围更新 l e f t left left，否则更新 r i g h t right right。因为每次循环中都保证了第 k 小的数在  l e f t − r i g h t left-right left−right 之间，当  l e f t = = r i g h t left == right left==right 时，第 k 小的数即被找出，等于 r i g h t right right.

**为什么对值二分**

*  二分查找可以根据索引二分，也可以根据数值二分，有序数组中，索引的大小可以反映值的大小，对索引二分就行
 *  但这里不是有序的一维数组，索引不能体现值谁大谁小，无法通过二分索引逼近目标值

**统计矩阵中小于中间值的元素个数**

*  以列为单位找，找到每一列最后一个<=mid的数即知道每一列有多少个数<=mid

参考链接：\[https://www.bilibili.com/video/BV1kK411n7Bi?from=search&seid=5093669144351830180\]

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
                   
            int m = matrix.length, n = matrix[0].length;
            int left = matrix[0][0], right = matrix[m - 1][n - 1];
            while(left < right){
         
                int mid = (left + right) / 2;
                int count = findSmall(matrix, mid, m, n);//求出小于mid的元素个数
                if(count < k){
        
                    left = mid + 1;
                }else{
        //大于等于k都使right=mid
                    right = mid;
                }
            }
            return right;//注意最后的临界条件是left == right
        }
    
        public int findSmall(int[][] matrix, int mid, int m, int n){
        
            // 以列为单位找，找到每一列最后一个<=mid的数即知道每一列有多少个数<=mid
            int count = 0;
            int i = m - 1, j = 0;//从左下角开始查找
            while(i >= 0 && j < n){
        
                if(matrix[i][j] <= mid){
        
                    count += i + 1; //将该列剩下的个数累加，并挪至下一列
                    j++;
                }else{
        
                    i--; //上移一行
                }
            }
            return count;
        }
    }

*  时间复杂度： O ( n l o g ( r − l ) ) O(nlog(r-l)) O(nlog(r−l))，二分查找次数为 O ( l o g ( r − l ) ) O(log(r-l)) O(log(r−l))，每次操作时间复杂度为 O ( n ) O(n) O(n)

--------------------

### 剑指offer 03.数组中重复的数字（简单） ###

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
    [2, 3, 1, 0, 2, 5, 3]
    输出：2 或 3

**方法一：利用集合的去重性**

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
            Set<Integer> set = new HashSet<>();
            int repeat = -1;
            for(int num : nums){
        
                if(!set.add(num)){
        
                    repeat = num;
                    break;
                }
            }
            return repeat;
        }
    }

*  时间复杂度： O ( N ) O(N) O(N)
 *  空间复杂度： O ( N ) O(N) O(N)

**方法二：利用原地排序置换**(萝卜-坑：每个坑放对应的萝卜，即对应索引放对应数字)

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
            int temp;
            for(int i=0;i<nums.length;i++){
        
                while (nums[i]!=i){
        
                    if(nums[i]==nums[nums[i]]){
        
                        return nums[i];
                    }
                    temp=nums[i];
                    nums[i]=nums[temp];
                    nums[temp]=temp;
                }
            }
            return -1;
        }
    }

*  时间复杂度： O ( N ) O(N) O(N)
 *  空间复杂度： O ( 1 ) O(1) O(1)(但是会修改原数组)

--------------------

### 645.错误的集合（简单） ###

集合 s 包含从 **1 到 n** 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

输入：nums = [1,2,2,4]
    输出：[2,3]

输入：nums = [2,2]
    输出：[2,1]

在数组  a r r arr arr 中，索引代表数字， a r r arr arr 存储每个数字出现的次数。例如  a r r \[ i \] arr\[i\] arr\[i\]存储数字 i i i出现的次数

(**萝卜-坑**：每个坑放对应的萝卜，即对应索引放对应数字出现的次数)

class Solution {
        
        public int[] findErrorNums(int[] nums) {
         
            //使用额外数组来存储每个元素出现的个数，注意因为存储的元素是1~n，所以定义它的长度为n+1，这样使其索引1~n正好对应这n个整数
           int[] arr = new int[nums.length + 1];
           int dup = -1, missing = 1;
           for(int num : nums){
        
               arr[num] ++; //遍历数组，出现某个整数，则arr的该索引对应数值加1，例如出现1，则arr[1] += 1;
    
           for(int i = 1; i < nums.length + 1; i++){
         //遍历arr的1~n索引
               if(arr[i] == 2){
        
                   dup = i;//若这个索引对应值为2，则说明i是重复出现的数字
               }
               if(arr[i] == 0){
        
                   missing = i;//索引为0说明i是缺失的
               }
           }
           return new int[]{
        dup, missing};
        }
    }

##### 复杂度分析： #####

*  时间复杂度： O ( N ) O(N) O(N)，遍历nums数组需要时间 O ( N ) O(N) O(N)，检查每个数字需要时间 O ( N ) O(N) O(N)；
 *  空间复杂度： O ( N ) O(N) O(N) 数组 a r r arr arr最多需要存储1~n个数字。

--------------------

### 287.寻找重复数（中等） ###

给定一个包含 `n + 1` 个整数的数组 `nums` ，其数字都在 `1` 到 `n` 之间（包括 `1` 和 `n`），可知至少存在一个重复的整数。

假设 `nums` 只有 **一个重复的整数** ，找出 **这个重复的数** 。

输入：nums = [1,3,4,2,2]
    输出：2

输入：nums = [3,1,3,4,2]
    输出：3

\*\*方法一：\*\*和上题类似，利用额外数组 a r r arr arr来存储每个元素出现的个数，出现两次以上的元素即为结果。但是该方法需要 O ( N ) O(N) O(N) 的空间复杂度，怎样可以只用常量级 `O(1)` 的额外空间解决这个问题呢？

**方法二：**二分查找，定义 c o u n t \[ i \] count\[i\] count\[i\]表示数组中小于等于 i i i的数有多少个，假设重复的数为 t a r g e t target target，那么 \[ 1 , t a r g e t − 1 \] \[1,target-1\] \[1,target−1\]里的所有数满足 c o u n t \[ i \] ≤ i count\[i\]≤i count\[i\]≤i， \[ t a r g e t , n \] \[target,n\] \[target,n\]里的所有数满足 c o u n t \[ i \] > i count\[i\]>i count\[i\]>i，具有单调性。（以示例1为例）

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5dTGuUJS-1618151363183)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210326165902019.png)\]][img-5dTGuUJS-1618151363183_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210326165902019.png]

class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int n = nums.length;
            int left = 0, right = n - 1;
            while(left <= right){
        
                int mid = left + (right - left)/2;
                int count = 0;
                for(int i = 0; i < n; i++){
        
                    if(nums[i] <= mid) count++;//从mid开始计算小于它的数字有多少个
                }
                if(count > mid) right = mid - 1;//如果count[mid] > mid，说明重复的数字在左边
                else
                    left = mid + 1;
            }
            return left;
        }
    }

**方法三：**快慢指针  
参考链接：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/

public int findDuplicate(int[] nums) {
        
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
        
            slow = nums[slow];
            fast = nums[nums[fast]];//快指针走两步，慢指针走一步，直到相遇
        }
        fast = 0;//相遇后，再将快指针放回起点，然后依次走一步
        while (slow != fast) {
        
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

--------------------

### 697.数组的度（简单） ###

给定一个非空且只包含非负数的整数数组 `nums`，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 `nums` 中找到与 `nums` 拥有相同大小的度的最短连续子数组，返回其长度。

输入：[1, 2, 2, 3, 1]
    输出：2
    解释：
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.

输入：[1,2,2,3,1,4,2]
    输出：6

\*\*解题思路：\*\*首先用哈希表记录每个数组元素出现的个数，以及第一次出现和最后一次出现的索引位置。然后循环遍历数组找到最高频数，并记录其为数组的度。接着遍历循环，从哈希表获取每个元素出现的频数，若等于数组的度，则记录其最后一次和第一次出现的索引的差，最后取差的最小值。

class Solution {
        
        public int findShortestSubArray(int[] nums) {
        
            Map<Integer, Integer> numsCnt = new HashMap<>();
            Map<Integer, Integer> numsLastIndex = new HashMap<>();
            Map<Integer, Integer> numsFirstIndex = new HashMap<>();
            for(int i = 0; i < nums.length; i++){
        
                int num = nums[i];
                numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
                numsLastIndex.put(num, i);//重复添加会用新值覆盖旧值
                if(!numsFirstIndex.containsKey(num)){
        
                    numsFirstIndex.put(num, i);
                }
            }
            int maxCnt = 0;
            for(int num : nums){
        
                maxCnt = Math.max(maxCnt, numsCnt.get(num));//数组的度（指数组里任一元素出现频数的最大值）
            }
    
            int ret = nums.length;
            for(int i = 0; i < nums.length; i++){
        
                int cnt = numsCnt.get(nums[i]);//获取每个元素的频数
                if(cnt != maxCnt) continue;
                ret = Math.min(ret, numsLastIndex.get(nums[i]) - numsFirstIndex.get(nums[i]) + 1);//找到最小值
            }
          return ret;
        }
    }

--------------------

### 766.托普利茨矩阵（简单） ###

给你一个 `m x n` 的矩阵 `matrix` 。如果这个矩阵是托普利茨矩阵，返回 `true` ；否则，返回 `false`

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 **托普利茨矩阵** 。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c1NRnEpx-1618151363183)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210325221015858.png)\]][img-c1NRnEpx-1618151363183_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210325221015858.png]

输入：matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
    输出：true
    解释：
    在上述矩阵中, 其对角线为: 
    "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。 
    各条对角线上的所有元素均相同, 因此答案是 True 。

\*\*解题思路：\*\*根据定义，当且仅当矩阵中每个元素都与其左上角相邻的元素（如果存在）相等时，该矩阵为托普利茨矩阵。因此，我们遍历该矩阵，将每一个元素和它左上角的元素相比对即可。

class Solution {
        
        public boolean isToeplitzMatrix(int[][] matrix) {
        
            int m = matrix.length, n = matrix[0].length;
            if(matrix == null || m == 0 || n == 0) return false;
            for(int i = 1; i < m; i++){
        
                for(int j = 1; j < n; j++){
        
                    if(matrix[i][j] != matrix[i-1][j-1]){
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

--------------------

### 565.数组嵌套（中等） ###

索引从`0`开始长度为`N`的数组`A`，包含`0`到`N - 1`的所有整数。找到最大的集合`S`并返回其大小，其中 `S[i] = {A[i], A[A[i]], A[A[A[i]]],... }`且遵守以下的规则

假设选择索引为`i`的元素`A[i]`为`S`的第一个元素，`S`的下一个元素应该是`A[A[i]]`，之后是`A[A[A[i]]]...` 以此类推，不断添加直到`S`出现重复的元素。

输入: A = [5,4,0,3,1,6,2]
    输出: 4
    解释: 
    A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
    
    其中一种最长的 S[K]:
    S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

\*\*解题思路：\*\*方法一：暴力求解【超过时间限制】

方法二：记录访问过的位置，\[参考链接\]\[https://leetcode-cn.com/problems/array-nesting/solution/javaqiu-jie-de-si-kao-yu-gai-jin-by-zackqf/\]

class Solution {
        
        public int arrayNesting(int[] nums) {
        
           int result = 0;
            for(int i=0;i<nums.length;i++){
        
                int count=0, k=i;
                while(nums[k]!=-1){
         //已经访问过的位置不用再计算
                    count++;
                    int tmp = nums[k];
                    nums[k] = -1;//已经访问过的位置置为-1
                    k = tmp;//接着嵌套遍历
                }
                result = Math.max(result,count);
            }
            return result;
        }
    }

--------------------

### 769.最多能完成排序的块（中等） ###

数组`arr`是`[0, 1, ..., arr.length - 1]`的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

输入: arr = [4,3,2,1,0]
    输出: 1
    解释:
    将数组分成2块或者更多块，都无法得到所需的结果。
    例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

输入: arr = [1,0,2,3,4]
    输出: 4
    解释:
    我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
    然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

\*\*解题思路：\*\*从数组左边开始遍历，若前 k k k个元素的为 \[ 0 , 1 , . . . , k − 1 \] \[0,1,...,k-1\] \[0,1,...,k−1\]（不分顺序, 即前 k k k个元素的最大值为 k − 1 k-1 k−1（等于数组末位索引值），则其可以进行升序排列，说明可以分为一块，当判断前 k + 1 k+1 k\+1个元素能否分块时，则只需判断前 k + 1 k+1 k\+1个元素的最大值是否为 k k k即可。

class Solution {
        
        public int maxChunksToSorted(int[] arr) {
        
            //当遍历到第i个位置时，如果可以切分为块，那前i个位置的最大值一定等于i。
            //否则，一定有比i小的数划分到后面的块，那块排序后，一定不满足升序。
            int res = 0, max = 0;
            for(int i = 0; i < arr.length; i++){
        
                max = Math.max(max, arr[i]);//统计前i个位置的最大元素
                if(max == i) res++;//若最大值等于末位索引，说明此处可以分块
            }
            return res;
        }
    }

1, 0\] 的结果是 \[3, 4, 0, 1, 2\]，这不是有序的数组。

输入: arr = \[1,0,2,3,4\]  
输出: 4  
解释:  
我们可以把它分成两块，例如 \[1, 0\], \[2, 3, 4\]。  
然而，分成 \[1, 0\], \[2\], \[3\], \[4\] 可以得到最多的块数。

**解题思路：**从数组左边开始遍历，若前$k$个元素的为$[0,1,...,k-1]$（不分顺序, 即前$k$个元素的最大值为$k-1$（等于数组末位索引值），则其可以进行升序排列，说明可以分为一块，当判断前$k+1$个元素能否分块时，则只需判断前$k+1$个元素的最大值是否为$k$即可。
    
    ```java
    class Solution {
        public int maxChunksToSorted(int[] arr) {
            //当遍历到第i个位置时，如果可以切分为块，那前i个位置的最大值一定等于i。
            //否则，一定有比i小的数划分到后面的块，那块排序后，一定不满足升序。
            int res = 0, max = 0;
            for(int i = 0; i < arr.length; i++){
                max = Math.max(max, arr[i]);//统计前i个位置的最大元素
                if(max == i) res++;//若最大值等于末位索引，说明此处可以分块
            }
            return res;
        }
    }

[img-hSRgN3BU-1618151363176_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210322211014900.png]: /images/20221022/6f7706f573c647b5aa1ab367d059e1d1.png
[img-JH7JKHMZ-1618151363178_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210322211504269.png]: /images/20221022/e5031a1eb618457fa31217f9721284bd.png
[img-eR73yHsM-1618151363179_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323202702150.png]: /images/20221022/7236a6aa4d654eb79841b3f882f190be.png
[img-aWFySPuS-1618151363180_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323202830287.png]: /images/20221022/6b3d63f8f4214321a5fd0aaf929472a1.png
[img-N5C1kr2v-1618151363181_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210323200156647.png]: /images/20221022/ba24a8a2d59944f981140029ed18a0f0.png
[img-5dTGuUJS-1618151363183_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210326165902019.png]: /images/20221022/c64ae5b677ff46c08c99a178c97d4fdc.png
[img-c1NRnEpx-1618151363183_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210325221015858.png]: /images/20221022/c230272db09c437eafabfc71b735ba25.png