数组&双指针.md

# 数组 / 双指针


**所谓双指针**

指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

## 加一

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。

**示例 :**

```java
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
```

#### 解题思路

只需要判断有没有进位并模拟出它的进位方式，如十位数加 11 个位数置为 00，如此循环直到判断没有再进位就退出循环返回结果。

然后还有一些特殊情况就是当出现 9999、999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。

![加一](https://img-blog.csdnimg.cn/20191016093738731.png)

#### 视频
[给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一](https://www.bilibili.com/video/av49075990?from=search&seid=3924446080902330615)

```java
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
```

<br>
<br>

----

## 删除元素

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

#### 解题思路

1. 定义一个 index 用于记录新数组下标，遍历数组
2. 如果与传入值不同，则其应存在于新数组中 index++ 并存入
3. 如果与传入值相同，说明重复，则直接跳过该数
4. 最后返回 index 即可

```java
public int removeElement(int[] A, int elem) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int index = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != elem) {
            A[index++] = A[i];
        } 
    }
    
    return index;
}
```

<br>
<br>

----

## 删除排序数组中的重复数字

在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。


**示例 :**

```java
给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
```

#### 解题步骤

1. 数组完成排序后，我们可以放置两个指针 size 和 i，其中 size 是慢指针，而 i 是快指针。
2. 只要 nums[size] = nums[i] ，我们就增加 i 以跳过重复项。
3. 当我们遇到 nums[i] =nums[size] 时，跳过重复项的运行已经结束
4. 因此我们必须把它（nums[i]）的值复制到 nums[size+1]。
5. 然后递增 i 接着我们将再次重复相同的过程，直到 size 到达数组的末尾为止。

![删除排序数组中的重复数字](https://img-blog.csdnimg.cn/20191016101459592.png)

```java
public int removeDuplicates(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int size = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != A[size]) {
            A[++size] = A[i];
        }
    }
    // (1)
    return size + 1;
}
```

注：因为 size 为下标，所以返回长度要加一

<br>
<br>

----

## 我的日程安排表 I

实现MyCalendar类来存储活动。如果新添加的活动没有重复，则可以添加。类将有方法book(int start，int end)。这代表左闭右开的间隔[start，end)有了预定，范围内的实数x，都满足start <= x < end，返回true。 否则，返回false，并且事件不会添加到日历中。

**示例 :**

```
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释: 
第一个日程安排可以添加到日历中.  第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20 。
```

#### 解题步骤

1. TreeMap 是一个有序的key-value集合，它通过 红黑树 实现，继承于AbstractMap，所以它是一个Map，即一个key-value集合。
2. TreeMap可以查询小于等于某个值的最大的key，也可查询大于等于某个值的最小的key。 
3. 元素的顺序可以改变，并且对新的数组不会有影响。

- floorKey(K key) 方法用于返回小于或等于给定的键的所有键中，的最大键，或null，如果不存在这样的键

- ceilingKey(K key) 方法用于返回大于或等于返回到给定的键中，的最小键，或null，如果不存在这样的键

```java
class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);
        if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}
```

<br>
<br>

----

## 合并两个有序数组

合并两个排序的整数数组A和B变成一个新的数组。可以假设A具有足够的空间去添加B中的元素。

**说明:**

初始化 A 和 B 的元素数量分别为 m 和 n。
你可以假设 A 有足够的空间（空间大小大于或等于 m + n）来保存 B 中的元素。

**示例:**

```java
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
```

#### 解题思路

- 双指针 / 从后往前
- 这里的指针 p 用于追踪添加元素的位置。

![图一](https://img-blog.csdnimg.cn/20191016111159584.png)
![图二](https://img-blog.csdnimg.cn/20191016111217724.png)

```java
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int i = m - 1, j = n - 1, index = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (A[i] > B[j]) {
            A[index--] = A[i--];
        } else {
            A[index--] = B[j--];
        }
    }
    while (i >= 0) {
        A[index--] = A[i--];
    }
    while (j >= 0) {
        A[index--] = B[j--];
    }
}
```

<br>
<br>

----

# Attention

- 为了提高文章质量，防止冗长乏味

### 下一部分算法题

- 本片文章篇幅总结越长。我一直觉得，一片过长的文章，就像一堂超长的 会议/课堂，体验很不好，所以我打算再开一篇文章

- 在后续文章中，我将继续针对`链表` `栈` `队列` `堆` `动态规划` `矩阵` `位运算` 等近百种，面试高频算法题，及其`图文解析  + 教学视频 + 范例代码`，进行深入剖析有兴趣可以继续关注 **[_yuanhao 的编程世界](https://juejin.im/user/5d00b2ee6fb9a07ef5622eed)**

- 不求快，只求优质，每篇文章将以 2 ～ 3 天的周期进行更新，力求保持高质量输出

<br>
<br>

-----

### 请点赞！因为你的鼓励是我写作的最大动力！

![请点赞](https://img-blog.csdnimg.cn/20191016135326393.jpg)

<br>
<br>

----