1、最多能完成排序的块

1、最多能完成排序的块

1.1、描述：

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。

示例： ```java 输入: 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] 可以得到最多的块数。对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

<a name="lxIms"></a>
## 1.2、个人思路：
> 先将数组排序，然后从数组两边进行遍历，将排序后的结果和原数组从**两边**进行比较，如果相等则返回结果加1，最终返回min（n, max）
- **代码**
```java
  public int maxChunksToSorted(int[] arr) {
   int n = arr.length;
    int[] b = Arrays.stream(arr).sorted().toArray();
    int max = 0;
    int front = 0;
    int rear = 0;
    for (int i = 0; i < n / 2; i++) {
        if (arr[i] == b[i]) {
            front++;
        }
        if (arr[n - i - 1] == b[n - i - 1]) {
            rear++;
        }
    }
       if ((front == n / 2 || rear == n / 2) ) {
        if (n % 2 != 0 && n>1){
            if (arr[n / 2 ] == b[n / 2]){
                max++;
            }
        }
    }
    max = max+front + rear + 1;
     return Math.min(max,n);
    }

存在的问题：没有注意数字和下标的关系，没有找到应有的数学关系，直接从两边进行计算，不能通过一些特殊实例。

1.3、官方
思路

定理一：对于某个块 AA，它由块 BB 和块 CC 组成，即 A = B + CA=B+C。如果块 BB 和块 CC 分别排序后都与原数组排序后的结果一致，那么块 AA 排序后与原数组排序后的结果一致。

证明：因为块 BB 和块 CC 分别排序后都与原数组排序后的结果一致，所以块 BB 的元素和块 CC 的元素的并集为原数组排序后在对应区间的所有元素。而 A = B + CA=B+C，因此将块 AA 排序后与原数组排序后的结果一致。

定理二：对于某个块 AA，它由块 BB 和块 CC 组成，即 A = B + CA=B+C。如果块 AA 和块 BB 分别排序后都与原数组排序后的结果一致，那么块 CC 排序后与原数组排序后的结果一致。

证明：如果块 CC 排序后与原数组排序后的结果不一致，那么块 BB 的元素和块 CC 的元素的并集不等同于原数组排序后在对应区间的所有元素。而块 AA 排序后与原数组排序后的结果一致，说明块 AA 的元素等同于原数组排序后在对应区间的所有元素。这与块 AA 的元素由块 BB 的元素和块 CC 的元素组成矛盾，因此块 CC 排序后与原数组排序后的结果一致。

代码 ```java class Solution { public int maxChunksToSorted(int[] arr) {

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

} }

<a name="sxqpr"></a>
## 1.4、总结
- 在数组相关的题目时，需要看数组下标和数组值的关系
- 特定题目的数学关系需要注意
<a name="wQL5l"></a>
# 2、使数组唯一的最小增量
<a name="mWmAD"></a>
## 1.1、描述：
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。
返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
- **示例：**
```java
输入：nums = [1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-increment-to-make-array-unique
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.2、个人思路：

1、创建一个新的数组用以记录每个数字出现的次数 2、遍历这个数组，对出现次数大于0的数字往前探测，然后将这个探测的数字设为一次，并使得记录减一，i—

代码

public int minIncrementForUnique(int[] nums) {
              int res=0;
      int len= nums.length;
      int temp[] = new int[nums.length*3];
      int tempLen=temp.length;
      for (int i = 0; i < len*3; i++) {
          temp[i] = -1;
      }
      for (int i = 0; i < len; i++) {
          temp[nums[i]]++;
      }
      for (int i = 0; i < tempLen; i++) {
          if (temp[i]>0){
              for (int j = 1; j < tempLen-i; j++) {
                  if (temp[i+j]==-1){
                          res=res+j;
                      temp[i+j]=0;
                      temp[i]--;
                      i--;
                      break;
                  }
              }
          }
      }
      return res;
  }

存在的问题：空间和时间复杂度都太高！！！

1.3、官方
力扣

尤其第三种方法

代码 ```java class Solution { int[] pos = new int [80000]; public int minIncrementForUnique(int[] A) {

  Arrays.fill(pos, -1); // -1表示空位
  int move = 0;
  // 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
  for (int a: A) {
      int b = findPos(a); 
      move += b - a;
  }
  return move;

}

// 线性探测寻址（含路径压缩） private int findPos(int a) {

  int b = pos[a];
  // 如果a对应的位置pos[a]是空位，直接放入即可。
  if (b == -1) { 
      pos[a] = a;
      return a;
  }
  // 否则向后寻址
  // 因为pos[a]中标记了上次寻址得到的空位，因此从pos[a]+1开始寻址就行了（不需要从a+1开始）。
  b = findPos(b + 1); 
  pos[a] = b; // 寻址后的新空位要重新赋值给pos[a]哦，路径压缩就是体现在这里。
  return b;

} }

作者：sweetiee 链接：https://leetcode.cn/problems/minimum-increment-to-make-array-unique/solution/ji-shu-onxian-xing-tan-ce-fa-onpai-xu-onlogn-yi-ya/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ```

1.4、总结

个人思路和线性探测一致，但线性探测之后的处理不一致，标准解法是直接算出路径，而我的是生成更新数组然后重新遍历。 :::info Arrays.fill(pos, -1); // -1表示空位 :::

学习资料

算法笔记

1、最多能完成排序的块

1.1、描述：

1.3、官方

1.2、个人思路：

1.3、官方

1.4、总结