【20190306】【每天一道算法题】移除元素

问题：

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

首先谈下我的看法：

我的思路是，对于 val=2 ，而 nums[8]={0,1,2,2,3,0,4,2} 这样的情况，我们可以逐个检查 nums[i] ，如果 nums[i]==val ，那么将最后一位元素赋值给当前的 nums[i]（就实现了删除当前等于 val 的这个元素，但注意同时不要跳过当前的 i ，要再一次进行检查！）

这样就存在一个问题，对于 val=3 ，而 nums[2]={3,3} 的情况（即所有元素都要删除的情况），这种想法实现不了！！！

/*按照我的思路编写的程序*/
#include<stdio.h>
#include<stdlib.h>

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

void main()
{
	int result;
	int nums[8]={0,1,2,2,3,0,4,2};
	result=removeElement(nums,8,2);

	printf("%d\n",result);
	//printf("%d",nums);   //这样无法正确输出数组！因为字符型数组可以一次性输出，但数值型数组需要循环输出！

	system("pause");
}

int removeElement(int* nums, int numsSize, int val)
{
    int *p=nums;
	int i,j;
	//for(;p!='\0';p++)
	for(i=0;i<numsSize;i++)
	{
		if(*p==val)
		{
			*p=nums[numsSize-1];
			numsSize--;
			
		}
		else
		{
			p++;   //只有当*p!=val时，p才加一，即向后移一位！
		}
	}
	return numsSize;
}
           

官方思路

1. 双指针

定义两个指针 i（慢指针）和 j（快指针），当 nums[j] 与 val 相等时，递增 j 以跳过该元素，只要 nums[j]!=val ，我们将 nums[j] 复制给 nums[i] ，同时递增两个索引，重复这个过程，直到 j 到达数组的末尾，该数组的新长度为 i 。

复杂度分析：

1. 时间复杂度：O(n) ，假设数组共有 n 个元素， i 和 j 至少遍历 2n 步。

2. 空间复杂度：O(1)（因为是“就地”、“原地”）。

2. 双指针——当要删除的元素很少时

就可以用我的思路，将当前元素与最后一个元素进行交换，并释放最后一个元素，注意：被交换的最后一个元素也可能是想要移除的值，所以对其要进行再一次检查！

复杂度分析：

1. 时间复杂度：O(n) ，i 和 j 最多遍历 n 步，这种方法中，赋值操作的次数等于要删除元素的个数。因此，如果要移除的元素很少时，该方法效率更高。

2. 空间复杂度：O(1)（因为是“就地”、“原地”）。

解答：

#include<stdio.h>
#include<stdlib.h>

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

void main()
{
	int nums[2]={3,3};
	int result;
	result=removeElement(nums,2,3);

	printf("%d\n",result);
	//printf("%d",nums);  // 如何输出数组

	system("pause");
}

int removeElement(int* nums, int numsSize, int val)  //用指针（效率更高，即所用时间短）
{
	int *i=nums,*j=nums;
	int n,m=0;
	for(n=0;n<numsSize;n++)   //n用来计循环次数
	{
		if(*j!=val)
		{
			*i=*j;
			i++;
			m++;   //m用来表示最终数组有几位
		}
		j++;
	}
	return m;
}

//int removeElement(int* nums, int numsSize, int val)  //用数组
//{
//	int i=0,j=0;
//	for(;j<numsSize;)
//	{
//		if(nums[j]!=val)
//		{
//			nums[i]=nums[j];
//			i++;
//		}
//		j++;
//	}
//	return i;
//}
           

知识点：

1. 注释：Ctrl+K+C；

2. 取消注释：Ctrl+K+U；

3. 编译错误：【找到一个或多个多重定义的符号】它说你定义了两个main，你得工程中有“源.cpp"和“源2.cpp”，在一个工程中，不允许有两个源文件分别定义main，需要删除一个。（即，不能在同一个工程里面定义两个main函数！）

同类型题目：

删除排序数组中的重复项