濮阳市网站建设,个人建站软件,wordpress多个主页,公司网站建设一条顺序表必备的三道面试题#xff08;附图解#xff09; 文章目录顺序表必备的三道面试题#xff08;附图解#xff09;前言一、第一题1.题目2.思路图解3.源码二、第二题1.题目2.思路图解3.源码三、第三题1.题目2.思路图解3.源码总结前言
本文给大家介绍三道顺序表学习过程中…顺序表必备的三道面试题附图解 文章目录顺序表必备的三道面试题附图解前言一、第一题1.题目2.思路图解3.源码二、第二题1.题目2.思路图解3.源码三、第三题1.题目2.思路图解3.源码总结前言
本文给大家介绍三道顺序表学习过程中Leedcode上的OJ题附源码和图解 一、第一题
1.题目 题目如下示例 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。//接口型
int removeElement(int* nums, int numsSize, int val)
{
}2.思路图解
思路一通过遍历找到所有的val一次挪动数据覆盖删除(时间复杂度O(N^2)),不符合题意。 能否将时间复杂度变成 O(N) 呢? 思路2一次遍历nums数组把不是val的值放到tmp数组再把tmp数组的值拷贝回去。如下图 这样处理的时间复杂度为O(2N)-O(N)空间复杂度O(N) 以空间换时间 能否将空间复杂度优化到 O(1) 呢 思路3请看图解 3.源码 代码如下示例 int removeElement(int* nums, int numsSize, int val)
{int src0;int dst0;while(srcnumsSize){if(nums[src]!val){nums[dst]nums[src];src;dst;}else{src;}}return dst;
}二、第二题
1.题目 代码如下示例 一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,
返回删除后数组的新长度,元素的 相对顺序应该保持一致由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分.
更规范地说如果在删除重复项之后有k个元素那么nums的前k个元素应该保存最终结果。将最终结果插入nums的前k个位置后返回k不要使用额外的空间你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。int removeDuplicates(int* nums, int numsSize)//接口型
{
}2.思路图解
思路一挪动数据如果有重复的元素就把重复后的元素前挪一步时间复杂度:O(N^2)),不符合题意 思路二再开辟一个数组如果重复的元素跳过去把没重复的元素移到新数组里 这样处理的时间复杂度为O(2N)-O(N)空间复杂度O(N) 以空间换时间不符合题意 思路三如下图解释 3.源码 代码如下示例 int removeDuplicates(int* nums, int numsSize)
{int i0;int j1;int dst0;if(numsSize0){return;}while(jnumsSize){if(nums[i]nums[j]){j;}else{nums[dst]nums[i];dst;ij;j;}}nums[dst]nums[i];dst;return dst;
}三、第三题
1.题目 题目如下示例 给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素目。请你 合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况
nums1的初始长度为m n其中前m个元素表示应合并的元素后n个元素为0应忽略。nums2的长度为n。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
}2.思路图解
这里就直接讲最终的思路和解法如下图图解所示 3.源码 代码如下示例 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1m-1;int end2n-1;int endmn-1;while(end10 end20){if(nums1[end1] nums2[end2]){nums1[end--]nums1[end1--];}else{nums1[end--]nums2[end2--];}}while(end20){nums1[end--]nums2[end2--];}
}总结
以上就是今天要讲的内容本文介绍了学习顺序表中的三道面试题以及图解源代码 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
