妇科医院网站建设,pos机网站建设方案,shopee个人开店条件,做网站技术要求怎么写主页#xff1a;114514的代码大冒 qq:2188956112#xff08;欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ #xff09; Gitee#xff1a;庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录
文章目录
前言
一、删除有序数组中的重复项
二、合并两个有序数组
三#xff0c;移除… 主页114514的代码大冒 qq:2188956112欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ Gitee庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录
文章目录
前言
一、删除有序数组中的重复项
二、合并两个有序数组
三移除元素
总结 前言
都是比较容易想明白的题目加油吧 一、删除有序数组中的重复项
表述
给你一个 升序排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度所以必须将结果放在数组nums的第一部分。更规范地说如果在删除重复项之后有 k 个元素那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
来源力扣LeetCode链接https://leetcode.cn/problems/remove-duplicates-from-sorted-array著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
示例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 。不需要考虑数组中超出新长度后面的元素。 思路一
建立一个足够大的新数组然后遍历一遍题目给的数组将其内容拷贝到新数组遇到要删除的值就跳过然后再将新数组的全部内容拷贝到题给数组如此时间复杂度为ON空间复杂度ON空间复杂度不符合题意
如图 思路二
使用双指针假设一个为dst(存储最终答案)另一个为str辅助删选
我们的逻辑是起始位置两指针都指向首元素如果str指向的元素等于dst指向的元素str
如果不相等说明是非重复数字将str指向的元素赋值到dst的下一个位置
如图 代码
int removeDuplicates(int* nums, int numsSize){int dst 0;int str 0;while(str numsSize){if(nums[dst] nums[str]){str;}else{nums[dst] nums[str];}}return dst 1;
} 二、合并两个有序数组
表述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
来源力扣LeetCode链接https://leetcode.cn/problems/merge-sorted-array著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
示例一 输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。 示例二 输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。 示例三 输入nums1 [0], m 0, nums2 [1], n 1 输出[1] 解释需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 思路
从两个数组的有效末尾元素位置倒着遍历设置两个指针分别指向两个数组各自的有效元素未知的末尾然后进行比较较大的元素被复制到nums1数组的末尾然后指针继续推进同时也会用指针标记nums1数组的末尾当指向位置存储正确数值后指针推进
如图 注意这里我们是数组2先完成了元素放置而数组1的元素顺理成章的可以呆在原位置但是如果是数组2都是较小值或者说是数组1的元素先完成了归位这时我们就需要单独处理数组2剩余元素了毕竟题目的要求是最终nums1存放真正的答案
代码
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int numsSize mn-1;//这是那个所谓的绿色指针int nums11 m - 1;//标记第一个数组的末尾int nums22 n - 1;//标记第二个数组的末尾while((nums11 0)(nums22 0)){if(nums1[nums11]nums2[nums22]){nums1[numsSize] nums1[nums11];numsSize--;nums11--;}else{nums1[numsSize] nums2[nums22];numsSize--;nums22--;}}//单独处理数组2的剩余元素while(nums22 0){nums1[numsSize] nums2[nums22];numsSize--;nums22--;}
}
三移除元素
表述
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
来源力扣LeetCode链接https://leetcode.cn/problems/remove-element著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
示例一 输入nums [3,2,2,3], val 3 输出2, nums [2,2] 解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。 示例二 输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3] 解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 思路由于空间复杂度的要求我们只能在原数组的基础上进行修改以满足题意我们仍对本题使用双指针一个用来辅助另一个负责记录
如图 代码
int removeElement(int* nums, int numsSize, int val){int src 0;int dst 0;if(numsSize 0){return 0;}while(dst numsSize){if(nums[dst] ! val){nums[src] nums[dst];dst;src;}else{dst;}}return src;
} 总结
本篇主要涉及双指针这是一种重要的做题思路
ok,这就是本次的全部题目了招待不周我们下期见
