算法详解：杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项

---

前言：本次分享题目全部来自力扣网，大家可以自行选择挑战，详细链接：

118. 杨辉三角 - 力扣（LeetCode）

88. 合并两个有序数组 - 力扣（LeetCode）

26. 删除有序数组中的重复项 - 力扣（LeetCode）

目录

一.杨辉三角

思路：

完整代码：

二.合并俩个有序数组

思路：

完整代码：

三.删除有序数组中的重复项

思路：

完整代码：

---

一.杨辉三角

题目：给定一个非负整数?numRows，生成「杨辉三角」的前?numRows?行（1 <= numRows <= 30）

注意：在「杨辉三角」中，每个数是它左上方和右上方的数的和

示例一：

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

?示例二：

输入: numRows = 1
输出: [[1]]

思路：

我们可以将杨辉三角图形进行转个方向，改为一个阶梯型的可能更适合我们理解，对于这样的阶梯型的数据，我们很自然就会联想到二维数组，那杨辉三角可不可以用二维数组实现呢？

对于每一行数据，第一个和最后一个都是1，剩下的数据都是上一行的同一位置的数据加上前一个数据，也就是说我们在实现每一行的数据的时候都需要用到上一行的数据。为了更高效的完成上述的过程我们可以使用二维的顺序表代替二维数组进行操作。

在确定了使用二维顺序表后，我们需要定义一个总的顺序表去存放每一行对应的顺序表，用外层for循环确定到底有多少行，用内层for循环确定每一行的元素，以上就确定了本题的大概框架。

对于几个细节需要注意：

总结观察杨辉三角，所有1的位置都是在每一行的开头和结尾，开头很简单内层for循环的 j=0?；的时候就是开头位置，而每一行的最后一个元素，我们仔细观察他的坐标就会发现，他的行数和列数相等，也就是外层for循环的循环变量 i 与内层for循环变量 j 相等的时候，总结来说当循环变量 (j == 0 || j == i) 的时候我们就对行顺序表添加元素 “1”?

对于非1的数据，我们需要访问上一行的数据，通过 .get( i-1) 可以拿到上一行的顺序表，拿到上一行的顺序表后再分别拿到这一行的 j 位置和 j-1 位置的元素，然后相加，相加后的结果就是我们要的值，最后再将这个值使用 .add 添加到这一行的顺序表中就可以

完整代码：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            //新定义一行
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                }else {
                    //添加上一行的数据（上一行的j-1和j位置）
                    row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
                }
            }
            //每一次将新的一行加入总的二维顺序表中
            ret.add(row);
        }
        return ret;
    }
}

---

二.合并俩个有序数组

题目：给你两个按?非递减顺序?排列的整数数组?nums1?和?nums2，另有两个整数?m?和?n?，分别表示?nums1?和?nums2?中的元素数目。请你?合并?nums2?到?nums1?中，使合并后的数组同样按?非递减顺序?排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组?nums1?中。为了应对这种情况，nums1?的初始长度为?m + n，其中前?m?个元素表示应合并的元素，后?n?个元素为?0?，应忽略。nums2?的长度为?n?。

示例一：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 

示例二：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 

?示例三：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1]

思路：

对于一个数组，我们要将其合并到一个全新的数组中，我们可以使用俩个指针，分别指向俩个数组，然后对比俩个指针谁的值小，小的值就放入新数组中，并且指针后移

对于放入数据一共有4种情况，我们分别对应处理一下：

1. nums1 的数据小于?nums2 的数据：将?nums1 的数据放入新数组，并且指针pA后移
2. nums1 的数据大于?nums2 的数据：将?nums2 的数据放入新数组，并且指针pB后移
3. nums1 的数据已经排除完了，但是?nums2 还有元素：将?nums2 的元素放入新数组，并且指针pB后移
4. ?nums2 的数据已经排除完了，但是?nums1 还有元素：将nums1的元素放入新数组，并且指针pA后移

我们使用一个while循环来包含所有的情况遍历，然后每一次判断都将一个数据通过临时变量放入新数组中，为了和服题目要求，将最后的结果再覆盖到数组1中

完整代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pA = 0;
        int pB = 0;
        int cur = 0;
        int[] sordNum = new int[m + n];
        while (pA < m || pB < n) {
            if (pA == m) {//nums1已满,放入nums2
                cur = nums2[pB++];
            } else if (pB == n) {//nums2已满，放入nums1
                cur = nums1[pA++];
            } else if (nums1[pA] < nums2[pB]) {//nums1的数据小于nums2
                cur = nums1[pA++];
            } else {//nums1的数据大于等于nums2
                cur = nums2[pB++];
            }
            sordNum[pA + pB - 1] = cur;
        }
        for (int j = 0; j != m + n; ++j) {
            nums1[j] = sordNum[j];
        }
    }
}

---

三.删除有序数组中的重复项

题目：给你一个?非严格递增排列?的数组?nums?，请你?原地?删除重复出现的元素，使每个元素?只出现一次?，返回删除后数组的新长度。元素的?相对顺序?应该保持?一致?。然后返回?nums?中唯一元素的个数。

示例一：

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

示例二：

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

思路：

对于这里的删除，我们可以巧妙的利用，具体来说我们可以将不重复的元素放在数组前面，然后我们只返回这部分不重复的元素，这样就变相的达到了删除的目标

完整代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        //快慢指针
        int left = 0;
        int right = 1;
        while(right < nums.length){
            if(nums[left] != nums[right]){
                left++;
                nums[left] = nums[right];
            }
            right++;
        }
        return left + 1;
    }
}

---

---

---

??本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见