题目练习之数组的那些事儿
学习了这么久C语言知识，也了解了算法的一些概念，我们可以通过一些题目检验自己是否真正的掌握，我们一起来看看下面的练习~
练习一：合并两个有序数组
合并两个有序数组： https://leetcode.cn/problems/merge-sorted-array/description/
打开题目链接，这是一道来自力扣的题目，阅读题目，要将两个非递减数组（升序数组）合并，同时要把nums2整个数组放到nums1数组里面。题目特别给出了nums1的长度是m+n，后面n元素为0。
我们通过他给的例子来更好地理解：
也就是说nums1中前面m个元素是nums1原来的数据，后面n个元素初始化为0，以便后面合并nums2的数据。那我们很快就可以用下面这个思路——先合并再排序
思路1
先把nums2数组的元素放到nums1中的后半部分，再对nums1数组进行排序
排序方法有很多，这里展示两种：
冒泡排序
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i = 0;
//先合并
for(i = m ; i< m + n ; i++)
{
nums1[i] = nums2[i-m];
}
//排序
int j = 0;
int temp = 0;
for(i = 0;i < m + n -1; i++)
{
for(j = 0; j < m + n - 1 -i; j++)
{
if(nums1[j+1]<nums1[j])
{
temp = nums1[j+1];
nums1[j+1] = nums1[j];
nums1[j] = temp;
}
}
}
}
提交代码可以看到它通过了测试
快速排序（qsort）
int cmp_int(void const* p1, void const* p2)
{
return (*(int*)p1 - *(int*)p2);
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i = 0;
//先合并
for (i = m; i < m + n; i++)
{
nums1[i] = nums2[i - m];
}
//排序
qsort(nums1, m + n, sizeof(nums1[0]), cmp_int);
}
提交代码也是成功通过，同时我们可以看到它的时间复杂度是小于冒泡排序的，这个题有没有什么其他方法也可以优化时间复杂度变成O(N)呢？这就需要我们的下一个思路了。
思路2
既然后面是元素0，那么我们可以将两个数组从后面开始向前走进行比较，哪一个数组元素大，就把哪一个元素放在后面再往前面走。
我们可以写出下面的代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//记录每一个数组原来最后一个下标
int l1 = m - 1;
int l2 = n - 1;
//记录合并数组最后一个下标
int index = m + n - 1;
while (l1 >= 0 && l2 >= 0)//保证数组下标不越界
{
//比较放入数据
if (nums1[l1] > nums2[l2])
{
nums1[index--] = nums1[l1--];
}
else
{
nums1[index--] = nums1[l2--];
}
}
}
但是当我们提交时，它告诉我们解答错误，我们在代码中来看看这个错误的案例
nums1没有元素，nums2有一个元素 m=0，n=1 l1=0-1=-1 l2=0 l1已经越界，无法进入循环，nums2中有元素还没有放到nums1中
//nums1没有元素，nums2有一个元素
//m=0，n=1
//l1=0-1=-1
//l2=0
//l1已经越界，无法进入循环
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//记录每一个数组原来最后一个下标
int l1 = m - 1;
int l2 = n - 1;
//记录合并数组最后一个下标
int index = m + n - 1;
while (l1 >= 0 && l2 >= 0)//保证数组下标不越界
{
//比较放入数据
if (nums1[l1] > nums2[l2])
{
nums1[index--] = nums1[l1--];
}
else
{
nums1[index--] = nums2[l2--];
}
}
}我们怎么样来处理这一种特殊情况呢？
解决方案： 当l1已经越界，nums2中有元素还没有放到nums1中时，我们可以再写一个循环将nums2的元素放到nums1中
正确代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//记录每一个数组原来最后一个下标
int l1 = m - 1;
int l2 = n - 1;
//记录合并数组最后一个下标
int index = m + n - 1;
while (l1 >= 0 && l2 >= 0)//保证数组下标不越界
{
//比较放入数据
if (nums1[l1] > nums2[l2])
{
nums1[index--] = nums1[l1--];
}
else
{
nums1[index--] = nums2[l2--];
}
}
while (l2 >= 0)
{
nums1[index--] = nums2[l2--];
}
}
练习二：删除有序数组中的重复项
这也是一道来自力扣的题目。
删除有序数组中的重复项： https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
题目给出了原地删除，那我们就不能通过创建一个新数组来实现了。
这个题目我们知道数组是有序的，并且是一个升序数组，重复的元素一定是在一起的，所以我们可以这样做：
双指针法（双变量法） 创建两个变量pcur、dest，下标表示不同的位置， dest是初始位置下标，pcur是初始位置的下一个位置的下标 将两个位置的数据进行比较，有两种情况： 如果相等，pcur就往后面走（pcur++） 如果不相等，dest++，将pcur的值赋给dest，pcur继续往后面走（pcur++） 最后返回新数组的长度
代码如下：
int removeDuplicates(int* nums, int numsSize)
{
//定义两个变量
int dest = 0;//初始位置下标
int pcur = dest + 1;//初始位置的下一个位置的下标
while (pcur < numsSize)
{
//比较
if (nums[dest] == nums[pcur])//跳过，pcur++
{
pcur++;
}
else//dest++，pcur赋值给dest后，再往后面走
{
dest++;
nums[dest] = nums[pcur];
pcur++;
}
}
return dest + 1;
//返回新数组长度
}
上面代码有点啰嗦，我们可以简单优化一下：
int removeDuplicates(int* nums, int numsSize)
{
//定义两个变量
int dest = 0;//初始位置下标
int pcur = dest + 1;//初始位置的下一个位置的下标
while (pcur < numsSize)
{
if (nums[dest] != nums[pcur] && ++dest != pcur)
{
nums[dest] = nums[pcur];
}
pcur++;
//pcur往后面走
}
return dest + 1;
//返回新数组长度
}
练习三：移除元素
移除元素： https://leetcode.cn/problems/remove-element/description/
题目也是给出了原地删除，那我们就不能通过创建一个新数组来实现。
我们也可以使用 双指针法(双变量法）
创建两个变量 pcur、dest指向初始位置的下标 将pcur数据与val进行比较，有两种情况： 如果相等，pcur就往后面走（pcur++） 如果不相等，将pcur的值赋给dest，pcur、dest往后面走（pcur++、dest++） 最后返回元素个数，也就是dest（dest前面已经++，不需要再+1）
int removeElement(int* nums, int numsSize, int val)
{
//创建两个变量下标指向初始位置
int pcur = 0;
int dest = 0;
while (pcur < numsSize)
{
if (nums[pcur] == val)//跳过
{
pcur++;
}
else//保留
{
nums[dest++] = nums[pcur++];
//dest、pcur使用后++
}
}
return dest;
//返回元素个数，dest前面已经++
}
我们可以看到运行通过~
♥♥♥本篇博客内容结束，期待与各位未来的优秀程序员交流，有什么问题请私信♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
腾讯云开发者
