数组相关的面试题

移除元素

方法一

我们可以设置俩个位置分别从起点开始，不等于val就加加，等于val的时候就str++,一直到sz停止。

int main()
{
	int arr[] = { 0,1,2,2,3,0,4,2 };
	int str = 0;
	int dst = 0;
	int vals = 2;
	int sz = sizeof(arr) / sizeof(arr[0]);
	while (str < sz)
	{
		if (arr[str] != vals)
		{
			arr[dst] = arr[str];
			str++;
			dst++;
		}
		else
		{
			str++;
		}
	}
	for (int i = 0; i < dst; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

方法二
我们可以自己在开辟一个数组，然后把不等于val的元素放进去，也是可行的，但是这个算法的效率没有刚刚的好。

int main()
{
	int arr[] = { 0,1,2,2,3,0,4,2 };
	int str = 0;
	int dst = 0;
	int vals = 2;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int* tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	while (str < sz)
	{
		if (arr[str] != vals)
		{
			memcpy(&tmp[dst], &arr[str], sizeof(int));
			str++;
			dst++;
		}
		else
		{
			str++;
		}
	}
	memcpy(arr, tmp, sizeof(int) * dst);
	for (int i = 0; i < dst; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

删除数组的中的重复项

这个题目的思路和刚刚题目方法一的差不多。

稍微有点区别就是dst的位置跟str起始位置不一样，如果都在起始位置就相当于前面有俩个0，不符合题目的要求了，我们把str放在1的位置上，我们在dst时候可以使用前置++，这样就可以让dst先跳过一个在被覆盖。

int main()
{
	int arr[] = { 0,0,1,1,1,2,2,3,3,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int str = 1;
	int dst = 0;
	while (str < sz)
	{
		if (arr[str] != arr[dst])
		{
			arr[++dst] = arr[str++];
		}
		else
		{
			str++;
		}
	}
	for (int i = 0; i < dst + 1; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

合并俩个有序数组

在这边我们可以先了解一下归并算法。

给定俩个数组，分别比较他们的大小，小的那个可以尾插到新数组，相等的话，随便哪个都可以。最后剩下的拷贝新数组就行。

在这个题目中我们这样比较会发现一个问题

这样子比较就会变成1 2 2 2 2 2 5 6不符合题目的要求了，
我们可以从后面往前面比较就行了，然后按照归并算法的要求，从前往后往前是比较小的，从后往前我们可以比较大的，这样的话，我们还是递增的了。

在图中我们可以发现一直到end2结束，这个就基本归并结束了，但是假如我们换个数据将end2换成-1 -2 7我们可以发现end2结束不了，end1先走完了，因此我们要考虑俩种情况。

int main()
{
	int nums1[] = { 1,2,3,0,0,0 };
	int nums2[] = {2,5,6};
	int sz1 = sizeof(nums1) / sizeof(nums1[0]);
	int sz2 = sizeof(nums2) / sizeof(nums2[0]);
	int end1 =(sz1/2)-1;
	int end2 = sz2 - 1;
	int dst = sz2 +(sz1/2) - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[dst] = nums1[end1];
			dst--;
			end1--;
		}
		else
		{
			nums1[dst] = nums2[end2];
			dst--;
			end2--;
		}
	}
	while (end2 >= 0)
	{
		nums1[dst] = nums2[end2];
		dst--;
		end2--;
	}
	for (int i = 0; i < sz1; i++)
	{
		printf("%d ", nums1[i]);
	}
	printf("\n");
	return 0;
}

如有错误请指出，谢谢。