个人网站做装修可以吗,安装网站程序,洛阳网百姓呼声,正规的网站制作平台提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 目录 前言 经典算法OJ题1#xff1a; 移除元素 解法一、逐个判断 解法二、双指针覆盖 经典算法OJ题2#xff1a; 合并两个有序数组 OJ题分为两个类型#xff1a; 总结 前言… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 目录 前言 经典算法OJ题1 移除元素 解法一、逐个判断 解法二、双指针覆盖 经典算法OJ题2 合并两个有序数组 OJ题分为两个类型 总结 前言
世上有两种耀眼的光芒一种是正在升起的太阳一种是正在努力学习编程的你!一个爱学编程的人。各位看官我衷心的希望这篇博客能对你们有所帮助同时也希望各位看官能对我的文章给与点评希望我们能够携手共同促进进步在编程的道路上越走越远! 提示以下是本篇文章正文内容下面案例可供参考
经典算法OJ题1 移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
首先要想清楚移除的本质并不是真删除而是把元素覆盖即可覆盖n个元素后数组总长度就要-n
解法一、逐个判断 把数组从头开始遍历找到目标元素val就执行一次任意位置删除 注意 在实际写代码时每删除一次元素i 都要回退一次因为有的测试用例是 3 3 3 3val 3如果不回退直接覆盖会少删两个元素。
代码演示:
void Erase(int* nums, int pos, int len)
{assert(len 0);while (pos len){nums[pos] nums[pos 1];//数组中后面的数据把前面的数据覆盖pos;//向后移动}
}
int removeElement(int* nums, int numsSize, int val)
{assert(nums); //nums不能为空指针int i 0;int len numsSize;//数组的有效元素个数for (i 0; i len; i){if (nums[i] val){Erase(nums, i, len);i--;//这里i--是因为后面的值把i所在的位置覆盖//如果不--出了这个循环i, 就会把再i上赋的值给忽略少判断一次len--;}}return len;//返回的是删除之后的数组长度
}
解法二、双指针覆盖
这是一种比较巧妙的解法用到了双指针 对数组内元素进行覆盖具体实现为存在两个指针src 、dst 两者初始都指向数组起始位置遍历 整个数组对指针 src 和指针 dst 所指向的值进行比较如果 *src ! val 就把 *src 赋给 *dst 然后 dst 向后移动当然无论相等还是不相等src 都需要往后移动这个解法的目的就是把数组中所有非目标值的元素往前移动最后返回 dst 的下标dst的下标就是数组中不等于 val 的值的个数 代码演示
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;}}return dst;
}
经典算法OJ题2 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 nums1 数组123000下标012345
nums2 数组256下标012
假设比小的思路设L1为nums1数组的起始位置L2为nums2数组的起始位置我们从比小的角度看L1为1时L2为2L2大L1此时L1为2L2为2我们假设还是L1的2大L1此时L1为3L2为2我们把L2的值赋给L1那么原来L1位置上的3就没了所以这种比小的思路是不行的。
假设比大的思路设L1为nums1数组实际有效数据的最后一个元素下标为2L3为nums1数组初始化的最后一个位置下标为5L2为nums2数组的最后一个元素L2为6时L1为3L2赋值给L3L2--,L3--L2不变;L2为5时L1为3L2赋值给L3L2--,L3--L1不变;L2为2时L1为3此时L1赋值给L3L3--,L1--;L2为2L1为2假设L2的2比L1的2要大L2赋值给L3L3--,L2--;此时L2已经完成循环所以比大的思路时正确的。
此外我们仍需要考虑两种情况L2先出循环和L1先出循环。
上面的比大思路就是我们的L2先出循环没有是什么好考虑的。
我们来看L1先出循环的情况
nums1 数组456000下标012345
nums2 数组123下标012
仍然是比大的思路L2为3时L1为6L1的值赋给L3L1--,L3--,L2不变L2为3时L1为5L1的值赋给L3L3--,L1--,L2不变L1为4时L2为3L1的值赋给L3L3--,L1--,L2不变此时L1先完成循环但是L2的数据还在原位因为都是递增的排序那么只需要把L2数组的元素赋值给L3中。
代码演示
void merge(int* nums1, int m, int* nums2, int n)
{int l1 m - 1, l2 n - 1;int l3 m n - 1;while (l1 0 l2 0){if (nums1[l1] nums2[l2]){nums1[l3] nums1[l1];l1--;l3--;}else{nums1[l3] nums2[l2];l3--;l2--;}}while (l2 0){nums1[l3] nums2[l2];l3--;l2--;}
}
OJ题分为两个类型 1接口型不需要main()函数我们把代码提交之后后端会自动拼接main()函数 2IO型需要main()函数 总结
好了本篇博客到这里就结束了如果有更好的观点请及时留言我会认真观看并学习。不积硅步无以至千里不积小流无以成江海。
