文章目录一、原地移除数组中的指定元素LC27问题描述解题思路代码实现复杂度分析二、合并两个有序数组(LC88)问题描述解题思路代码实现复杂度分析一、原地移除数组中的指定元素LC27原地移除数组中的指定元素问题描述解题思路这道题的关键在于原地操作也就是说我们不能使用额外的数组空间必须在原数组上进行修改。最直接的想法是遍历数组当遇到等于val的元素时就将其删除但数组的删除操作其实是通过后面的元素向前移动来实现的这样会导致时间复杂度较高。更高效的方法是使用双指针技术创建两个变量分别是scr 0dst 0作为下标如果src指向的值为val则src如果src指向的值不是val则将src指向的值赋值给dst指向的值,src,dst遍历结束后dst的值就是不等于val的元素的数量代码实现intremoveElement(int*nums,intnumsSize,intval){intsrc0;intdst0;while(src!numsSize){if(nums[src]!val){nums[dst]nums[src];src;dst;}else{src;}}returndst;}复杂度分析时间复杂度O(n)其中 n 是数组的长度。我们只需要遍历一次数组。空间复杂度O(1)只使用了常数级别的额外空间。这种方法的优点是高效且简洁通过一次遍历就完成了所有操作并且不需要额外的空间。二、合并两个有序数组(LC88)合并两个有序数组问题描述解题思路这道题要求合并两个有序数组并且要将结果存储在第一个数组中。如果从前往后合并可能会覆盖nums1中还未处理的元素这就需要额外的空间来保存这些元素。更好的方法是从后往前合并定义三个指针i指向nums1有效元素的末尾m-1j指向nums2的末尾n-1k指向合并后数组的末尾mn-1比较nums1[i]和nums2[j]的大小将较大的元素放到nums1[k]的位置然后相应地移动指针当其中一个数组的元素全部处理完毕后将另一个数组中剩余的元素复制到 nums1 的前面注意当i 0或j 0会跳出循环。当j 0说明num2已经全部移入num1数组而num1数组本身就是有序的此时整个数组就是有序的状态不需要再处理当i 0跳出循环只需要依次把num2中剩余元素移入num1中代码实现voidmerge(int*nums1,intm,int*nums2,intn){intim-1;intjn-1;intkmn-1;while(i0j0){if(nums1[i]nums2[j]){nums1[k]nums1[i];i--;k--;}else{nums1[k]nums2[j];j--;k--;}}while(j0){nums1[k]nums2[j];k--;j--;}}复杂度分析时间复杂度O(m n)需要遍历两个数组的所有元素空间复杂度O(1)只使用了常数级别的额外空间