三（1）OJ题：原地移除数组中所有的元素val

三（1）OJ题：原地移除数组中所有的元素val

目录

题目

解答

思路1：暴力求解，多次循环

思路2：使用额外的数组

思路3：双指针

---

题目

力扣https://leetcode-cn.com/problems/remove-element/点击上面网址可查看原题

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

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

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

解答 思路1：暴力求解，多次循环

这个题目暴力的解法就是两层for循环，第一个循环遍历数组元素 ，第二个循环更新数组。

很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    while(i 
思路2：使用额外的数组 
 
 
开辟一个临时数组，依次遍历nums数组，把不是val的值放到tmp数组，再把tmp的值拷贝回去
 
 
时间复杂度到O(N)了，但是空间复杂度也是O(N)了，经典的空间换时间
 
 
int removeElement(int* nums, int numsSize, int val){
    int* tmp=(int*)malloc(sizeof(int)*numsSize);
    int j=0;
    for(int i=0;i 
思路3：双指针 
 
 
由于题目要求删除数组中等于val的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。 
 
 
可以使用双指针：右指针right指向当前将要处理的元素，左指针left指向下一个将要赋值的位置。
 
 
如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
 
 
如果右指针指向的元素等val，它不能在输出数组里，此时左指针不动，右指针右移一位。
 
 
整个过程保持不变的性质是：区间[0,left)中的元素都不等于val。当左右指针遍历完输入数组以后，left的值就是输出数组的长度。
 
 
 
 
这样的算法在最坏情况下（输入数组中没有元素等于val），左右指针各遍历了数组一次,时间复杂度为O(N)。
 
 
int removeElement(int* nums, int numsSize, int val){
    int left=0,right=0;
    while(right					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5595080.html