顺序表算法题（C语言）_可以用顺序表解决的c语言题

---

1、删除有序数组中的重复项（力扣26题）

---

题目要求：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间（意思是不能创建新的数组），你必须在 原地（原来的数组） 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

---

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

---

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

---

方法一：快慢指针
因为要使每个元素仅出现一次，所以第一个元素必定会保留，我们的快慢指针初始位置就在第二个位置上。
所以要做数组为空的特殊判断
快指针的作用：在数组中往后寻找，并把指向的值与慢指针指向的前一个位置的值进行对比
慢指针的作用：当做标记，可以理解为新的已排序好的数组的最后一位，他能把每个与他前面数不同的数给搬进来

如果相同，则跳过继续往后找，直到找到不同的值

当快指针找到和慢指针的前一位不同的值后，把值复制给慢指针指向的位置，慢指针再往后移一位，快指针再继续找

代码部分

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0)
        return numsSize;
    int slow = 1;
    int fast = 1;
    while(fast < numsSize)
    {
        if( nums[fast] != nums[slow - 1])
        {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

2、删除有序数组中的重复项 II （力扣80题）

---

题目要求：给你一个有序（升序）数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

---

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

---

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

---

方法一：快慢指针
和第一题差不多，但是这题要求的是可以有两个是相同的，所以我们的快慢指针起点是在第三位 而快指针是与慢指针前数第二个位置的数进行比较的，当快指针指向的数与被比较的数一样时，就说明有两个以上的数相同，所以快指针就要往下移动跳过一样的值，去寻找不一样的值，找到后就把慢指针所指的值覆盖。

if (numsSize <= 2) {
        return numsSize;
    }
    int slow = 2, fast = 2;
    while (fast < numsSize) {
        if (nums[slow - 2] != nums[fast]) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;

1
2
3
4
5
6
7
8
9
10
11
12
13