数据结构初步（四）- oj练习-线性表之顺序表

前言

前面学习了顺序表的相关概念后，让我们来会会这几个题！

1. 移除元素

1.1 题目链接

力扣（LeetCode）链接：移除元素

1.2 题目要求

给你一个数组

和一个值

，你需要 原地 移除所有数值等于

的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用

额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

//

是以“引用”方式传递的。也就是说，不对实参作任何拷贝

;

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。

for (int i = 0; i < len; i++) {
    print(nums[i]);
}

1.3 代码框架

int removeElement(int* nums, int numsSize, int val){
    
}

1.4 思路分析

给定一个数组

，遇到与

的数组元素相等就去掉，不相等就保留，假设

是数组

中与

相等元素的个数，则修改后的数组前

个位置是存放非

的有效位置。

题目要求空间复杂度是

，不能开辟额外的临时数组空间。

我们可以把题目所给的原数组

当作修改元素后的新数组，两个变量记录数组下标，假设

记录原数组下标，

记录新数组下标；

记录原数组中与

相等的元素个数。

开始时

的下标都是

，分别对应新旧数组的第一个位置，如果

位置的元素等于

，

均往后后移动一位；否则，就把

位置元素放入

位置处，然后

往后移动一位。直到旧数组被

遍历一遍。

时间复杂度

空间复杂度

1.5 代码实现

int removeElement(int* nums, int numsSize, int val){
    int p1=0;
    int p2=0;
    int count = 0;//重复的数的个数
    //初始下标p1与p2均为0
    //下标p1遍历整个旧数组，下标p2指向新数组

    while(p1 < numsSize){
        if(nums[p1] != val){
            nums[p2++] = nums[p1++];
        }
        else{
            ++p1;
            ++ccount;
        }
    }
    return numsSize - count;
}

2. 移除元素

2.1 题目链接

力扣（LeetCode）链接：删除有序数组中的重复项

2.2 题目要求

一个 升序排列 的数组

，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组

的第一部分。更规范地说，如果在删除重复项之后有

个元素，那么

的前

个元素应该保存最终结果。 将最终结果插入

的前

个位置后返回

。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用

额外空间的条件下完成。 判题标准:

//系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1： 输入：

输出：

解释：函数应该返回新的长度

， 并且原数组

的前五个元素被修改为

。不需要考虑数组中超出新长度后面的元素。 提示：

已按 升序 排列

2.3 代码框架

int removeDuplicates(int* nums, int numsSize){ 
}

2.4 思路分析

题目要求对有序数组进行去重处理，并且不开辟额外的临时数组，那么思路是把题目所给的数组

当作去重后的新数组即可。

使用变量

记录原数组的下标，使用变量

记录新数组的下标,使用变量

记录重复元素的个数；

原数组中第一个元素我们默认直接放入了新数组的第一个位置，所以我们直接把

初始化为1，记录原数组可能存在的第二个元素的下标，

初始化为0，记录当前新数组的最后一个元素。

当

小于

时，进行判断： 如果

对应元素不等于

对应元素，则

先记录新数组下一个位置的下标再把

位置元素移动到

位置，更新

为原数组下一个位置的下标。 如果

对应元素等于

对应元素，说明新数组中已经存在该元素，故跳过该元素，

记录原数组数组下一个位置的下标，

不变，

自增

。

当

等于

时说明去重完毕；

时间复杂度

空间复杂度

2.5 代码实现

int removeDuplicates(int* nums, int numsSize){
    int old = 1;
    int new = 0;
    int count = 0;
    while(old < numsSize){
        if(nums[old] == nums[new]){
            ++old;
            ++count;
        }
        else{
            nums[++new] = nums[old++];
        }
    }
    return numsSize - count;
}

3. 移除元素

3.1 题目链接

力扣（LeetCode）链接：合并两个有序数组

3.2 题目要求

给你两个按 非递减顺序 排列的整数数组

和

，另有两个整数

和

，分别表示

和

中的元素数目。 请你 合并

到

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

示例 1： 输入：

输出：

解释：需要合并

和

。 合并结果是

，其中斜体加粗标注的为

中的元素。 示例 2： 输入：

输出：

解释：需要合并

和

。 合并结果是

。 示例 3： 输入：

输出：

解释：需要合并的数组是

和

。 合并结果是

。 注意，因为

，所以

中没有元素。

中仅存的

仅仅是为了确保合并结果可以顺利存放到

中。 提示：

进阶：你可以设计实现一个时间复杂度为

的算法解决此问题吗？

3.3 代码框架

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
}

3.4 思路分析

采用归并排序的思想，对两个数组元素依次进行比较，但是因为比较后的结果要存入第一个数组

,并且不借助临时数组存放结果，所以我们对这两个数组的比较不能从前往后进行，这样可能会把

中未排序的数给覆盖掉；应该从后往前倒着对两个数组进行归并排序。

整型变量

、

分别记录原数组

、

的下标；

记录新数组的下标，实际上其也是记录数组

，称呼为新旧数组只是为了好区分而已。

当

大于等于

并且

大于等于

，说明可以进行两个数组可以进行比较： 找出

对应原数组元素与

对应原数组元素的较大者，将其移动到

对应新数组位置，之后更新对应原数组下标变量

或

，更新新数组下标变量

。

当

小于

或者

小于

，说明至少有一个数组的元素已经全部移动到了新数组； 如果是原数组

元素没有全部移动到新数组，就把

中剩余元素移动到新数组； 如果是原数组

元素没有全部移动到新数组，就什么也不用做，因为新数组中的元素实际上是直接存入了原数组

中，当原数组

全部元素移动完成就可以看成已经结束了。

时间复杂度

空间复杂度

3.5 代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int old1 = m-1;//旧数组1的下标old1
    int old2 = n-1;//旧数组2的下标old2
    int new = nums1Size-1;//新数组1的下标
    //归并排序思想，但不能从前往后开始排序，而要反过来从后往前排序。因为会覆盖未排序元素。
    //当有一个数组的下标小于0，说明某一个旧数组元素已经全部移动到新数组了，结束循环
    while(old1 >= 0 && old2 >= 0){
        if(nums1[old1] > nums2[old2]){
            nums1[new] = nums1[old1];
            --old1;
            --new;
        }
        else{
            nums1[new] = nums2[old2];
            --old2;
            --new;
        }
    }
    //因为新数组就是旧数组1，只需旧数组2的全部元素移动到新数组就完成了，即只考虑old2
    while(old2 >= 0){
        nums1[new] = nums2[old2];
        --new;
        --old2;
    }
}

结语

本文到这里就结束了，如果有错误之处欢迎批评指正！