石景山广州网站建设,优秀网站设计效果图,定时切换照片wordpress,客户管理系统网站2.3 数组相关面试题
原地移除数组中所有的元素val#xff0c;要求时间复杂度为O(N)#xff0c;空间复杂度为O(1)。OJ链接 力扣OJ链接-移除元素删除排序数组中的重复项。力扣OJ链接-删除有序数组中的重复项合并两个有序数组。力扣OJ链接-合并两个有序数组
2.3.1 移除元素
1…2.3 数组相关面试题
原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。OJ链接 力扣OJ链接-移除元素删除排序数组中的重复项。力扣OJ链接-删除有序数组中的重复项合并两个有序数组。力扣OJ链接-合并两个有序数组
2.3.1 移除元素
1. 题目描述
力扣OJ链接-移除元素 原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作
更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。
2. 分析 思路1另外开辟一个数组src从头往后遍历遇到不是要删除元素就把该元素赋值给数组直到遍历完整个数组在最后再把数组赋值到原数组。 思路2不另外开辟数组就在原数组进行操作 src从前往后遍历遇到不等于val的数就赋值给dst 然后src dst src遇到val ,不进行赋值直接srcdst不变 直到src遍历完整个数组 3. 思路2代码实现
int removeElement(int* nums, int numsSize, int val) {int src 0;int dst 0;while(srcnumsSize){if(nums[src]! val){nums[dst] nums[src];}else{src;}}return dst;
}2.3.2 删除重复元素
1. 题目描述
力扣OJ链接-删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与nums 的大小不重要。返回 k 。
2. 思路
这个和上一道题思路非常类似~重点是要分析这个判断相等如何设置。
3. 代码实现
int removeDuplicates(int* nums, int numsSize) {int str 1;int end 0;while(strnumsSize){if(nums[str] ! nums [end]){nums[end] nums[str];//这里先,如果后就会覆盖原本的值}else{str;} }return end1;
}进阶写法虽然代码量更短但是代码可读性差~ int removeDuplicates(int* nums, int numsSize) {int str 1;int end 0;while(strnumsSize){if(nums[str] ! nums [end])nums[end] nums[str];//这里end必须先,如果后就会覆盖原本的值str;} return end1;
}2.3.3 合并两个有序数组
1.题目描述
力扣OJ链接-合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
2. 思路 解题思路: 1. 从后往前遍历数组将nums1和nums2中的元素逐个比较 将较大的元素往nums1末尾进行搬移 2. 第一步结束后nums2中可能会有数据没有搬移完将nums2中剩余的元素逐个搬移到nums1 时间复杂度O(mn) 空间复杂度: O(1) 两种情况 情况1 情况2 3. 代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {// end1、end2分别标记nums1 和 nums2最后一个有效元素位置// end标记nums1的末尾因为nums1和nums2中的元素从后往前往nums1中存放// 否则会存在数据覆盖int end1 m-1;int end2 n-1;int dst mn-1;//合并后的数组长度是m n最后一个元素的位置就是 nums[mn-1]// 从后往前遍历将num1或者nums2中较大的元素往num1中end位置搬移// 直到将num1或者num2中有效元素全部搬移完while(end1 0 end2 0)//有一个小于1 就结束了循环写的是继续所以是{if(nums1[end1]nums2[end2]){nums1[dst--] nums1[end1--];}else{nums1[dst--] nums2[end2--];}}// num2中的元素可能没有搬移完将剩余的元素继续往nums1中搬移while(end2 0){nums1[dst--] nums2[end2--];}}
