移除数组中指定元素的所有数

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

思路1：暴力查找——覆盖法，遇到一次val就挪动后面的数据删除

代码

int removeElement(int* nums, int numsSize, int val)
{
	int i = 0;
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] == val)
		{
		
			int begin = i + 1;
			while (begin < numsSize)
			{
				nums[begin - 1] = nums[begin];//覆盖
				begin++;
			}
			numsSize--;//长度减1

		}
		
	}
	return numsSize;
}
int main()
{
	int nums[] = { 1,2,3,2,4,2,5,2,6 };
	int val = 2;
	int sz = sizeof(nums) / sizeof(nums[0]);
	int size = 0;
	size = removeElement(nums, sz, val);
	int j = 0;
	printf("%d\n", size);
	for (j = 0; j < size; j++)
	{
		printf("%d", nums[j]);
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

上述方法的时间复杂度为O（N^2）

思路2：用空间来换时间，另外开辟一个数组空间

int* removeElement2(int* nums, int numsSize, int val)
{
	int* p = (int*)calloc(numsSize,sizeof(int));
	int num = 0;
	int n = 0;
	for(int i=0;i<numsSize;i++)
	{
		if (nums[i] != val)
		{
			p[n] = nums[i];
			n++;
		
		}
		
	}
	printf("%d\n", n);

	int j = 0;
	for (j = 0; j < n; j++)
	{
		printf("%d", p[j]);
	}

	return 0 ;
}
int main()
{
	int nums[] = { 1,2,3,2,4,2,5,2,6 };
	int val = 2;
	int sz = sizeof(nums) / sizeof(nums[0]);
	int size = 0;
	//size = removeElement1(nums, sz, val);
	removeElement2(nums, sz, val);
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

思路3：原地移除，空间复杂度1，时间复杂度：O（N）

int removeElement3(int* nums, int numsSize, int val)
{
	int left = 0;
	int right = 0;
	for (right = 0; right < numsSize; right++)
	{
		if (nums[right] != val)
		{
			nums[left] = nums[right];
				left++;
			
		}
	}
	printf("%d\n", left);
		int j = 0;
	for (j = 0; j < left; j++)
	{
		printf("%d", nums[j]);
	}

	return 0 ;
}


int main()
{
	int nums[] = { 1,2,3,2,4,2,5,2,6 };
	int val = 2;
	int sz = sizeof(nums) / sizeof(nums[0]);
	int size = 0;
	//size = removeElement1(nums, sz, val);
	//removeElement2(nums, sz, val);
	removeElement3(nums, sz, val);

	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36