力扣（LeetCode）数据结构练习题

今天来分享两道力扣（LeetCode）的题目来巩固上篇时间复杂度和空间复杂度的知识，也就是在题目上加上了空间复杂度和时间复杂度的限制。

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略nums2 的长度为 n 。

给你一个数组 `nums` 和一个值 `val`，你需要原地移除所有数值等于 `val` 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 `O(1)` 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

我们注意审题发现这里要求O（1）的空间复杂度来完成，且在原地修改数组。不知道大家是否有了自己思路了呢。这道题的考点就是限制了空间复杂度和操作方式，那么有什么办法呢，下面是一种参考方法。

int removeElement(int* nums, int numsSize, int val) {


    int a=0;
    int b=0;
while(a<numsSize)
{
if(nums[a]!=val)
{
    nums[b]=nums[a];
    b++;
    a++;
}
else
{
    a++;
}

}


return b;
}

具体思路：我们就创建两个变量作为解体的关键，其中a作为遍历数组全部的变量，不断往后遍历，知道数组的元素全部遍历完成，即a==numsSize。在此过程中只要nums数组中的元素不等于val我们就从头开始不断往后覆盖掉原来的数即可。

此解法空间复杂度位O（1），时间复杂度为O（N）。

接下来我们看第二题

给你两个按非递减顺序排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。

请你合并 `nums2` 到 `nums1` 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况

`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略
`nums2` 的长度为 `n` 。

这里我们尽量将代码弄到更优且我们试试将时间复杂度控制为O（m+n），下面给出一种参考解法：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    
int end=m+n-1;
int end1=m-1;
int end2=n-1;
while(end1>=0 && end2>=0)
{
if(nums1[end1]>nums2[end2])
{

    nums1[end]=nums1[end1];
    end1--;
    end--;
}

else
{

nums1[end]=nums2[end2];
end2--;
end--;

}

}

while(end2>=0)
{

nums1[end]=nums2[end2];
end--;
end2--;

}


}

具体思路：这里我们从题目可知我们要将nums2合并到nums1中，其中nums1的长度为m+n，那么如果我们从nums1的前面开始排序，我们就会因为排序而丢失前面nums1原来的值，所以我们就要从末尾开始排序，所以我们在代码中先定义出三个整形变量end1，end2，end，分别进行运算，进行while循环在两个数组都没比较结束到首元素时我们进行比较后放入nums1的末尾，当有一个nums1的比较元素已经到首元素时，如果nums2的元素还没比较完，那么我们就需要将nums2的元素全排在前面即可。

这里的解法空间复杂度为O（m+n）,空间复杂度为O（1）

好了就分享这两道题了，这两道题主要控制时间复杂度和空间复杂度是相比以前的练习解法限制更多，锻炼我们写优质代码的能力。喜欢的话希望点个心心支持一次唔。