网站设计怎么做图片透明度黄浦区做网站

当前位置： 首页 > news >正文

网站设计怎么做图片透明度,黄浦区做网站,阿里云服务器租用多少钱一年,网站备案 代理目录 一、顺序表算法题 1、移除元素 2、删除有序数组中的重复项
3、 合并两个有序数组 二、顺序表问题与思考 一、顺序表算法题 1、移除元素 移除元素 - 力扣#xff08;LeetCode#xff09; 思路分析#xff1a; 思路一#xff1a;创建一个新数组#xff0c;开辟…目录 一、顺序表算法题 1、移除元素 2、删除有序数组中的重复项  3、 合并两个有序数组 二、顺序表问题与思考 一、顺序表算法题 1、移除元素 移除元素 - 力扣LeetCode 思路分析 思路一创建一个新数组开辟新空间把符合条件的元素放到新数组中再释放和销毁旧空间。 思路二用顺序表査找指定元素并返回该指定元素的下标再删除指定下标的位置。 思路三用一个顺序表查找指定元素逐个查找指定元素与符合条件的元素删除后面往前挪动一个位置。 我们现在以思路三来详细分析一下 第一层循环遍历数组查找val。 第二层循环val之后的数据整体往前挪动一位。 时间复杂度为O(n^2)对于需要查找多次的复杂算法题比较不友好运行时间长 但对于这一道带提示条件的简单算法题就没有时间限制的要求所以就无需关心时间复杂度。 但对于追求更高要求的时间和空间的相关算法复杂度的精度我们从以下思路来入手 最终思路 该思路的时间复杂度为O(n)空间复杂度为O(1)。 定义两个变量指向数组第一个位置判断nums[src]是否等于val所以有以下两者情况 1当nums[src]等于val所以src 2当nums[src]不等于val所以nums[dst]nums[src]srcdst。 我们就这个数组例子来分析一下 1因为nums[src]等于val所以src当src后nums[src]为数组第二个元素的位置nums[src]不等于valnums[dst]nums[src]此时数组第一个元素被赋值为2再srcdst。 2 当src和dst后nums[src]为数组第三个元素的位置nums[sdst]为数组第二个元素的位置。nums[src]不等于valnums[dst]nums[src]此时数组第二个元素被赋值为2再srcdst。 3 当src和dst后nums[src]为数组第三个元素的位置nums[dst]为数组第二个元素的位置。此时nums[src]等于val所以src。 4 此时nums[src]在后面数组外超出数组的范围即可为不满足src小于numsSize的条件跳出循环返回dst值。 运行代码  int removeElement(int* nums, int numsSize, int val) {int src 0;int dst 0;while(src numsSize){if(nums[src] val){src;}else{nums[dst] nums[src];//dst;//src;}}//此时dst指向的位置就是要返回的有效个数return dst; } 运行提交结果 2、删除有序数组中的重复项  删除有序数组中的重复项 - 力扣LeetCode  思路分析 思路一指针指向第一个元素然后与它后面的元素进行比较若相等第一个元素和它后面的一个元素以外的整体前移若不相等则指针后移一位以此类推。 思路二定义两个变量dst为第一个位置src为第一个位置的下一个位置判断src和dst位置的数据因此有以下两者情况 1若相等src 2若不相等dstnums[dst]nums[src],src。 思路二只有一层循环时间复杂度为On空间复杂度为O1 我们以思路二的一个例子来入手分析一下 1此时nums[dst]nums[src]所以src此时src为第三个元素的位置。 2此时nums[dst] ! nums[src]则dst此时dst为第二个元素的位置所以使nums[dst]nums[src]再让src。 3此时nums[src]在后面数组外超出数组的范围即可为不满足src小于numsSize的条件跳出循环返回dst值。 总结规律 两个重复的元素必定相邻不可能中间有间隔的元素所以直接相当于把重复的元素删掉只保留不重复的元素保持有序性。 运行代码  int removeDuplicates(int* nums, int numsSize) {int dst 0, src dst1;while(src numsSize){//nums[dst] nums[src]//相同重复 src//不相同dst赋值srcif(nums[dst] ! nums[src] dst ! src){nums[dst] nums[src];}src;}return dst1; } 运行提交结果 3、 合并两个有序数组 合并两个有序数组 - 力扣LeetCode 思路分析 根据题目要求我们可以创建三个指针分别指向num1最后一个有效数据位置num2最后一个数据位置和num1最后一个位置比较了l1和l2位置的数据谁大谁就往l3位置放数据同时往l3放数据的这个指针和l3这个指针往前移动一个位置另一个指针不动继续以上操作。 结束条件以两种情况为主 1l10要处理nums2中数据循环放到num1中。 2l20不需要处理因为nums2中的数据已经有序的放到num1中了。 我们以该思路分析以下例子 最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 1l1和l2的数据相比较l1的数据大放到l3的位置处。 2同时l1和l3往前移动一个位置 l2不动。 3以此类推重复以上操作直到l1或l2其中之一指向数组之外。 情况一 此例子是l2指向数组之外即l20此时表明不需要处理因为nums2中的数据已经有序的放到num1中了。 情况二 我们以另一种情况来看即l10要处理nums2中数据循环放到num1中同时往l3放数据的这个指针和l3这个指针往前移动一个位置另一个指针不动。 该思路只有并列的两层循环时间复杂度为On或Om空间复杂度为O1 运行代码 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int l1 m - 1;int l2 n -1;int l3 m n - 1;//l1 0 l2 0while(l1 0 l2 0){if(nums1[l1] nums2[l2]){nums1[l3–] nums1[l1–];}else{//l1 l2 要么 l2 l1nums1[l3–] nums2[l2–];}}//跳出while有两种情况要么l1 0需要处理要么l2 0不需要处理while(l2 0){nums1[l3–] nums2[l2–];}
} 运行提交结果 进阶你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗  为了利用数组 nums 1与 nums 2已经被排序的性质我们可以使用双指针方法。这一方法将两个数组看作队列每次从两个数组头部取出比较小的数字放到结果中。 初始两数组状态如下 排序后的效果 运行代码 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 0, p2 0;int sorted[m n];int cur;while (p1 m || p2 n) {if (p1 m) {cur nums2[p2];} else if (p2 n) {cur nums1[p1];} else if (nums1[p1] nums2[p2]) {cur nums1[p1];} else {cur nums2[p2];}sorted[p1 p2 - 1] cur;}for (int i 0; i ! m n; i) {nums1[i] sorted[i];} }复杂度分析 时间复杂度O(mn)。指针移动单调递增最多移动 mn 次因此时间复杂度为 O(mn)。空间复杂度O(mn)。需要建立长度为 mn 的中间数组 sorted。 二、顺序表问题与思考 中间/头部的插入删除时间复杂度为O(N) 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 增容⼀般是呈2倍的增长势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到200 我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢这就需要引入链表的相关内容了请听下回博客详细分解。