Leetcode习题27:移除元素
题目:
说明:
示例:
题解:
方法一:(开辟额外的数组空间)
我们可以创建一个新的数组,然后用循环来遍历原数组,将原数组中不为 val 的值放到新数组之中去,然后通过新数组向屏幕上面打印相关数据。因为原题要求不使用额外的数组空间(原题中的 O(1)就是不能额外开辟空间),所以该方法不能用。
方法二:(使用指针)
我们首先创建两个变量,其中一个变量叫 src (源数据),另外一个变量叫 dst(目标数据)
当 src 指向的数据为 val 时,src 向后移动一位,dst 不采取任何操作src 和 dst 都向后移动一位;
当 src 指向的数据不为 val 时,src 和 dst 都向后移动一位,同时令 src 指向的值 = dst 指向的值;
当 src 遍历完数组里面所有的元素时,就停止 dst 的拷贝,此时有效值就是 dst 里面所有元素的个数
此时我们就可以写出代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
//给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
//
//不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//
//元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
int removeElement(int* nums, int numsSize, int val)
{
//创建两个变量
int src, dst;
src = dst = 0;
while (src < numsSize)//numsSize表示数组的长度
{
if (nums[src] == val)
{
src++;
}
else
{
//赋值两指针++
nums[dst] = nums[src];
dst++;
src++;
}
}
//此时dst的值刚好是新数组的有效长度
return dst;
}
Leetcode习题88:合并两个有效数组
题目:
示例:
题解:
根据题目可以知道:非递减数列本质上就是递增数列(除去相等数据)
由题意可知,nums1 的初始长度是 m + n,因为数组1中需要加入数组2的中的元素,若是长度小于 m + n 的话,则数组2中的所有元素不能够完全的添加进数组1
思路一:(排序)
将数组2中的数据依次放入到数组1的后面,使用排序算法对数组1进行排序(若是仅仅多次使用 for 循环的嵌套,那么将会导致程序效率低下的问题)
思路二:
例如:
有两个数组
num 1:
1 | 2 | 3 |
0 1 2 3 4 5
num2:
2 | 5 | 6 |
在两个数组之中分别定义三个变量 l1 和 l2 和 l3,将 l1 和 l2 变量都放在数组有效数据的最后一位,l3 变量放到数组1的最后一位,用 l1 和 l2 变量指向的值从后往前相互比较:(若是我们从前往后比较大小,数组里面的数据可能会存在覆盖问题)
从后往前比大小:比那个数据更大,大的数据往后放
若是 l2 (6)所指向的值大于 l1 (3)所指向的值,那么 l2 (6)代表的数据放到 l3 (【5】)的位置,l2 和 l3 再执行 -- 操作,向前挪动一位,l1 保持在原地不动;
接着比较当前位置 l2 (5)和 l1(3) 数据的大小,若此时 l2 仍旧大于 l1 ,则还是把 l2 代表的数据放到当前 l3 (【4】)的位置,l2 和 l3 再执行 -- 操作,向前挪动一位,l1 保持在原地不动;
若此时 l1 (3)所代表的值大于 l2 (2)所代表的值,则把当前位置 l1 的值放到 l3 (【3】)的位置,l3 和 l1 执行 --操作,向前挪动一位,l2 在原地保持不动;
若是 l2 和 l1 所代表的值相等,则任取一个;
由此类推,直到 num2 遍历完全部数组,则跳出循环;
此时还存在另外一种情况:
num1:
2 | 4 | 6 |
num2:
1 | 3 | 5 |
通过上述操作,我们可以推算出,l1 先出了循环,而 l2 此时还剩下一位,此事的情况为:
2 | 2 | 3 | 4 | 5 | 6 |
此时 num2 第一位所代表的数字 1 还没有拷贝到 num1 中去,但是此时 l1 已经先走出了循环,现在该怎么办呢?
此时我们应该把 l2 中剩余的数据放到 l3 中去,然后让 l2 和 l3 都采取 -- 操作,向前挪动一位,此时数组有序,成功完成任务。
此题目并不会出现 l1 和 l2 同时小于0的情况
综上所以我们可以写出函数如下:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//nums1Size:num1数组长度
//nums2Size:num2数组长度
//这两个没有用
{
int l1 = m - 1;
int l2 = n - 1;
int l3 = m + n - 1;
while (l1 >= 0 && l2 >= 0)//只要满足一个条件就跳出循环
{
if (nums1[l1] < nums2[l2])
{
nums1[l3--] = nums2[l2--];
}
else
{
nums1[l3--] = nums1[l1--];
}
}
//出了循环有两种情况l1 >= 0或者l2 >= 0
//只需要处理:l1 < 0 (l2的数据还没有全部放到num1中)
if (l2 >= 0)
{
nums1[l3--] = nums2[l2--];
}
//此时num1包含num2
}