数组面试题总结

Love The Way You Lie 2022-12-24 13:57 225阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 03. 数组中重复的数字
     *   *  解法
     *  剑指 Offer 53 - I. 在排序数组中查找数字 I
     *   *  解法
         *  二分查找另一种写法
     *  剑指 Offer 53 - II. 0～n-1中缺失的数字
     *   *  解法
         *  等差数列
         *  二分法
     *  移动零
     *   *  解法1
         *  解法2
     *  最大连续1的个数
     *   *  解法
     *  剑指 Offer 04. 二维数组中的查找
     *   *  解法
     *  有序矩阵中第K小的元素
     *   *  二分查找法
         *  堆排序
     *  剑指 Offer 29. 顺时针打印矩阵
     *   *  解法
     *  重塑矩阵
     *   *  解法
     *  错误的集合
     *   *  解法
     *  寻找重复数
     *   *  双指针
     *  优美的排列 II
     *   *  解法
     *  数组的度
     *   *  解法
     *  托普利茨矩阵
     *   *  解法
     *  数组嵌套
     *   *  解法
     *  最多能完成排序的块
     *   *  解法

## 剑指 Offer 03. 数组中重复的数字 ##

[力扣链接][Link 1]

找出数组中重复的数字。

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

示例 1：
    
    输入：
    [2, 3, 1, 0, 2, 5, 3]
    输出：2 或 3 
     
    
    限制：
    
    2 <= n <= 100000

### 解法 ###

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

## 剑指 Offer 53 - I. 在排序数组中查找数字 I ##

[力扣链接][Link 2]

统计一个数字在排序数组中出现的次数。

示例 1:
    
    输入: nums = [5,7,7,8,8,10], target = 8
    输出: 2
    示例 2:
    
    输入: nums = [5,7,7,8,8,10], target = 6
    输出: 0
     
    
    限制：
    
    0 <= 数组长度 <= 50000

### 解法 ###

用二分法找到第一次出现target的位置，然后遍历即可。

class Solution {
        
        public int search(int[] nums, int target) {
        
            int firstIndex = -1;
            if (nums.length == 0 || nums[0] > target) {
        
                return 0;
            }
            int low = 0, high = nums.length - 1;
            // 用二分查找，找到第一次出现target的位置
            while (low <= high) {
        
                int mid = low + ((high - low) >> 1);
                if (nums[mid] >= target) {
        
                    if (mid == 0 || (nums[mid] == target && nums[mid - 1] < target)) {
        
                        firstIndex = mid;
                        break;
                    }
                    else {
        
                        high = mid - 1;
                    } 
                }
                else {
        
                    low = mid + 1;
                }
            }
            if (firstIndex != -1 && nums[firstIndex] == target) {
        
                if (firstIndex == nums.length - 1) {
        
                    return 1;
                }
                else {
        
                    // 往下遍历找到第二次出现target 的位置
                    for (int i = firstIndex + 1; i < nums.length; ++i) {
        
                        if (nums[i] != target) {
        
                            return i - firstIndex; // i - 1 - firstIndex + 1
                        }
                        if (i == nums.length - 1 && nums[i] == target) {
        
                            return i - firstIndex + 1;
                        }
                    }
                }
            }
            return 0;
        }
    }

### 二分查找另一种写法 ###

class Solution {
        
        public int search(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while (left < right) {
        
                int mid = left + ((right - left) >> 1);
                if (nums[mid] < target) {
        
                    left = mid + 1;
                } else if (nums[mid] == target){
        
                    right = mid;
                } else {
        
                    right = mid - 1;
                }
            }
            int count = 0;
            while (left < nums.length && nums[left] == target) {
        
                left++;
                count++;
            }
            return count;
        }
    }

## 剑指 Offer 53 - II. 0～n-1中缺失的数字 ##

[力扣链接][Link 3]

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
    
    输入: [0,1,3]
    输出: 2
    示例 2:
    
    输入: [0,1,2,3,4,5,6,7,9]
    输出: 8
     
    
    限制：
    
    1 <= 数组长度 <= 10000

### 解法 ###

1 = 1 ^ 2 ^ 2;三个数做异或运算会除去相同的数。

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int result = 0;
            for (int i = 0; i < nums.length; ++i) {
        
                result = result ^ i ^ nums[i];
            }
            return result ^ nums.length;
        }
    }

### 等差数列 ###

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int n = nums.length;
            int sum = (n + 1) * n / 2;
            for (int num : nums) {
        
                sum -= num;
            }
            return sum;
        }
    }

### 二分法 ###

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int i = 0, j = nums.length - 1;
            while (i <= j) {
        
                int mid = i + ((j - i) >> 1);
                if (nums[mid] == mid) {
        
                    i = mid + 1;
                } else {
        
                    j = mid - 1;
                }
            }
            return i;
        }
    }

## 移动零 ##

[283. 移动零][283.]

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

示例:

输入: \[0,1,0,3,12\]  
输出: \[1,3,12,0,0\]  
说明:

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

### 解法1 ###

class Solution {
        
        public void moveZeroes(int[] nums) {
        
            int index = 0;
            for (int num : nums) {
        
                if (num != 0) {
        
                    nums[index++] = num;
                }
            }
            while (index < nums.length) {
        
                nums[index++] = 0;
            }
        }
    }

### 解法2 ###

class Solution {
        
        public void moveZeroes(int[] nums) {
        
            int index = 0;
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] != 0) {
        
                    nums[index++] = nums[i];
                    if (i != index - 1) {
        
                        nums[i] = 0;
                    }
                }
            }
        }
    }

## 最大连续1的个数 ##

[力扣链接][Link 4]

给定一个二进制数组， 计算其中最大连续1的个数。

示例 1:

输入: \[1,1,0,1,1,1\]  
输出: 3  
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.  
注意：

输入的数组只包含 0 和1。  
输入数组的长度是正整数，且不超过 10,000。

### 解法 ###

class Solution {
        
        public int findMaxConsecutiveOnes(int[] nums) {
        
            int max = 0, cur = 0;
            for (int x : nums) {
        
                cur = x == 0 ? 0 : cur + 1;
                max = Math.max(max, cur);
            }
            return max;
        }
    }

## 剑指 Offer 04. 二维数组中的查找 ##

[力扣链接][Link 5]

在一个 n \* m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:
    
    现有矩阵 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。
    
    给定 target = 20，返回 false。
    
     
    
    限制：
    0 <= n <= 1000
    0 <= m <= 1000

### 解法 ###

class Solution {
        
        public boolean findNumberIn2DArray(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 i = 0, j = n - 1;
            while (i < m && j >= 0) {
        
                int tmp = matrix[i][j];
                if (tmp > target) {
        
                    j--;
                } else if (tmp < target) {
        
                    i++;
                } else {
        
                    return true;
                }
            }
            return false;
        }
    }

## 有序矩阵中第K小的元素 ##

[378. 有序矩阵中第K小的元素][378. _K]

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

示例：
    
    matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,
    
    返回 13。

提示：  
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

### 二分查找法 ###

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 - left) / 2;
                int count = 0;
                for (int i = 0; i < m; i++) {
        
                    for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
        
                        count++;
                    }
                }
                if (count < k) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

### 堆排序 ###

维持一个小顶堆

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            int m = matrix.length, n = matrix[0].length;
            PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
            for (int j = 0; j < n; ++j) {
        
                pq.offer(new Tuple(0, j, matrix[0][j]));
            }
            for (int i = 0; i < k - 1; ++i) {
        
                Tuple t = pq.poll();
                if (t.x == m - 1) {
        
                    continue;
                }
                pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
            }
            return pq.poll().val;
        }
        class Tuple implements Comparable<Tuple> {
        
            int x, y, val;
            public Tuple(int x, int y, int val) {
        
                this.x = x;
                this.y = y;
                this.val = val;
            }
            @Override
            public int compareTo(Tuple tuple) {
        
                return this.val - tuple.val;
            }
        }
    }

## 剑指 Offer 29. 顺时针打印矩阵 ##

[力扣链接][Link 6]

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：
    
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]
    示例 2：
    
    输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     
    
    限制：
    
    0 <= matrix.length <= 100
    0 <= matrix[i].length <= 100

### 解法 ###

class Solution {
        
        public int[] spiralOrder(int[][] matrix) {
        
            if (matrix.length == 0) {
        
                return new int[0];
            }
            int row = 0, col = 0, m = matrix.length - 1, n = matrix[0].length - 1;
            int[] res = new int[(m+1) * (n+1)];
            int index = 0;
            while (true) {
        
                for (int i = col; i <= n; ++i) {
        
                    res[index++] = matrix[row][i];
                }
                if (++row > m) {
        
                    break;
                }
                for (int i = row; i <= m; ++i) {
        
                    res[index++] = matrix[i][n];
                }
                if (--n < col) {
        
                    break;
                }
                for (int i = n; i >= col; --i) {
        
                    res[index++] = matrix[m][i];
                }
                if (--m < row) {
        
                    break;
                }
                for (int i = m; i >= row; --i) {
        
                    res[index++] = matrix[i][col];
                }
                if (++col > n) {
        
                    break;
                }
            }
            return res;
        }
    }

## 重塑矩阵 ##

[566. 重塑矩阵][566.]

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

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

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:
    
    输入: 
    nums = 
    [[1,2],
     [3,4]]
    r = 1, c = 4
    输出: 
    [[1,2,3,4]]
    解释:
    行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
    示例 2:
    
    输入: 
    nums = 
    [[1,2],
     [3,4]]
    r = 2, c = 4
    输出: 
    [[1,2],
     [3,4]]
    解释:
    没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
    注意：
    
    给定矩阵的宽和高范围在 [1, 100]。
    给定的 r 和 c 都是正数。

### 解法 ###

class Solution {
        
        public int[][] matrixReshape(int[][] nums, int r, int c) {
        
            int row = nums.length, col = nums[0].length;
            if (row * col != r * c) {
        
                return nums;
            }
            int[][] res = new int[r][c];
            int index = 0;
            for (int i = 0; i < r; i++) {
        
                for (int j = 0; j < c; j++) {
        
                    res[i][j] = nums[index / col][index % col];
                    index++;
                }
            }
            return res;
        }
    }

## 错误的集合 ##

[645. 错误的集合][645.]

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

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

示例 1:
    
    输入: nums = [1,2,2,4]
    输出: [2,3]
    注意:
    
    给定数组的长度范围是 [2, 10000]。
    给定的数组是无序的。

### 解法 ###

第一个for循环将nums数组排好序，第二个for循环返回结果。

class Solution {
        
        public int[] findErrorNums(int[] nums) {
        
            for (int i = 0; i < nums.length; i++) {
        
                while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
        
                    swap(nums, i, nums[i] - 1);
                }
            }
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] != i + 1) {
        
                    return new int[]{
        nums[i], i + 1};
                }
            }
            return null;
        }
        private void swap(int[] nums, int i, int j) {
        
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

## 寻找重复数 ##

[287. 寻找重复数][287.]

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

示例 1:
    
    输入: [1,3,4,2,2]
    输出: 2
    示例 2:
    
    输入: [3,1,3,4,2]
    输出: 3
    说明：
    
    不能更改原数组（假设数组是只读的）。
    只能使用额外的 O(1) 的空间。
    时间复杂度小于 O(n2) 。
    数组中只有一个重复的数字，但它可能不止重复出现一次。

### 双指针 ###

把数组当成有环链表，此题变成寻找环入口。  
详细题解[https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/][https_leetcode-cn.com_problems_find-the-duplicate-number_solution_xun-zhao-zhong-fu-shu-by-leetcode-solution]

将这个题目给的特殊的数组当作一个链表来看，数组的下标就是指向元素的指针，把数组的元素也看作指针。如 0 是指针，指向 nums\[0\]，而 nums\[0\] 也是指针，指向 nums\[nums\[0\]\].

class Solution {
        
        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;
        }
    }

## 优美的排列 II ##

[667. 优美的排列 II][667. _ II]

给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
    
    ① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
    
    ② 如果存在多种答案，你只需实现并返回其中任意一种.
    
    示例 1:
    
    输入: n = 3, k = 1
    输出: [1, 2, 3]
    解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
     
    
    示例 2:
    
    输入: n = 3, k = 2
    输出: [1, 3, 2]
    解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2
     
    
    提示:
    
     n 和 k 满足条件 1 <= k < n <= 104.

### 解法 ###

让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 … k/2 k/2+1.

class Solution {
        
        public int[] constructArray(int n, int k) {
        
            int[] res = new int[n];
            res[0] = 1;
            for (int i = 1, interval = k; i <= k; i++, interval--) {
        
                res[i] = i % 2 == 1 ? res[i - 1] + interval : res[i - 1] - interval;
            }
            for (int i = k + 1; i < n; i++) {
        
                res[i] = i + 1;
            }
            return res;
        }
    }

## 数组的度 ##

[697. 数组的度][697.]

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

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

示例 1:
    
    输入: [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.
    示例 2:
    
    输入: [1,2,2,3,1,4,2]
    输出: 6
    注意:
    
    nums.length 在1到50,000区间范围内。
    nums[i] 是一个在0到49,999范围内的整数。

### 解法 ###

class Solution {
        
        public int findShortestSubArray(int[] nums) {
        
            Map<Integer, Integer> numsCount = 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];
                numsCount.put(num, numsCount.getOrDefault(num, 0) + 1);
                numsLastIndex.put(num, i);
                if (!numsFirstIndex.containsKey(num)) {
        
                    numsFirstIndex.put(num, i);
                }
            }
            int maxCount = 0;
            for (int num : nums) {
        
                maxCount = Math.max(maxCount, numsCount.get(num));
            }
            int result = nums.length;
            for (int num : nums) {
        
                int count = numsCount.get(num);
                if (count != maxCount) {
        
                    continue;
                }
                result = Math.min(result, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
            }
            return result;
        }
    }

## 托普利茨矩阵 ##

[766. 托普利茨矩阵][766.]

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

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

示例 1:
    
    输入: 
    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。
    示例 2:
    
    输入:
    matrix = [
      [1,2],
      [2,2]
    ]
    输出: False
    解释: 
    对角线"[1, 2]"上的元素不同。
    说明:
    
    matrix 是一个包含整数的二维数组。
    matrix 的行数和列数均在 [1, 20]范围内。
    matrix[i][j] 包含的整数在 [0, 99]范围内。
    进阶:
    
    如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
    如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？

### 解法 ###

先检查上三角矩阵，然后检查下三角矩阵

class Solution {
        
        public boolean isToeplitzMatrix(int[][] matrix) {
        
            for (int i = 0; i < matrix[0].length; i++) {
        
                if (!check(matrix, matrix[0][i], 0, i)) {
        
                    return false;
                }
            }
            for (int i = 1; i < matrix.length; i++) {
        
                if (!check(matrix, matrix[i][0], i, 0)) {
        
                    return false;
                }
            }
            return true;
        }
        private boolean check(int[][] matrix, int expectValue, int row, int col) {
        
            if (row >= matrix.length || col >= matrix[0].length) {
        
                return true;
            }
            if (matrix[row][col] != expectValue) {
        
                return false;
            }
            return check(matrix, expectValue, row + 1, col + 1);
        }
    }

## 数组嵌套 ##

[565. 数组嵌套][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出现重复的元素。
    
    示例 1:
    
    输入: 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}
     
    
    提示：
    
    N是[1, 20,000]之间的整数。
    A中不含有重复的元素。
    A中的元素大小在[0, N-1]之间。

### 解法 ###

class Solution {
        
        public int arrayNesting(int[] nums) {
        
            int max = 0;
            for (int i = 0; i < nums.length; i++) {
        
                int count = 0;
                for (int j = i; nums[j] != -1; ) {
        
                    count++;
                    int t = nums[j];
                    nums[j] = -1;
                    j = t;
                }
                max = Math.max(count, max);
            }
            return max;
        }
    }

## 最多能完成排序的块 ##

[769. 最多能完成排序的块][769.]

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

我们最多能将数组分成多少块？

示例 1:
    
    输入: arr = [4,3,2,1,0]
    输出: 1
    解释:
    将数组分成2块或者更多块，都无法得到所需的结果。
    例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
    示例 2:
    
    输入: arr = [1,0,2,3,4]
    输出: 4
    解释:
    我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
    然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
    注意:
    
    arr 的长度在 [1, 10] 之间。
    arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

### 解法 ###

class Solution {
        
        public int maxChunksToSorted(int[] arr) {
        
            if (arr == null) {
        
                return 0;
            }
            int result = 0;
            int right = arr[0];
            for (int i = 0; i < arr.length; i++) {
        
                right = Math.max(right, arr[i]);
                if (right == i) {
        
                    result++;
                }
            }
            return result;
        }
    }

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

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**

![gzh.jpg][]

[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[Link 2]: https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[Link 3]: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
[283.]: https://leetcode-cn.com/problems/move-zeroes/
[Link 4]: https://leetcode-cn.com/problems/max-consecutive-ones/description/
[Link 5]: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[378. _K]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
[Link 6]: https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
[566.]: https://leetcode-cn.com/problems/reshape-the-matrix/
[645.]: https://leetcode-cn.com/problems/set-mismatch/
[287.]: https://leetcode-cn.com/problems/find-the-duplicate-number/
[https_leetcode-cn.com_problems_find-the-duplicate-number_solution_xun-zhao-zhong-fu-shu-by-leetcode-solution]: https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
[667. _ II]: https://leetcode-cn.com/problems/beautiful-arrangement-ii/
[697.]: https://leetcode-cn.com/problems/degree-of-an-array/
[766.]: https://leetcode-cn.com/problems/toeplitz-matrix/
[565.]: https://leetcode-cn.com/problems/array-nesting/
[769.]: https://leetcode-cn.com/problems/max-chunks-to-make-sorted/
[gzh.jpg]: /images/20221120/35ec2e67c2624d38b1238cb63905640a.png