深圳做营销网站制作,昆明网络推广公司哪家好,装潢公司网站建设,广州网站建设便宜Leetcode习题27#xff1a;移除元素
题目#xff1a; 说明#xff1a; 示例#xff1a;
题解#xff1a;
方法一#xff1a;#xff08;开辟额外的数组空间#xff09;
我们可以创建一个新的数组#xff0c;然后用循环来遍历原数组#xff0c;将原数组中不为 val…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
123 0 1 2 3 4 5 num2
256 在两个数组之中分别定义三个变量 l1 和 l2 和 l3将 l1 和 l2 变量都放在数组有效数据的最后一位l3 变量放到数组1的最后一位用 l1 和 l2 变量指向的值从后往前相互比较若是我们从前往后比较大小数组里面的数据可能会存在覆盖问题
从后往前比大小比那个数据更大大的数据往后放
若是 l2 6所指向的值大于 l1 3所指向的值那么 l2 6代表的数据放到 l3 【5】的位置l2 和 l3 再执行 -- 操作向前挪动一位l1 保持在原地不动
接着比较当前位置 l2 5和 l13 数据的大小若此时 l2 仍旧大于 l1 则还是把 l2 代表的数据放到当前 l3 【4】的位置l2 和 l3 再执行 -- 操作向前挪动一位l1 保持在原地不动
若此时 l1 3所代表的值大于 l2 2所代表的值则把当前位置 l1 的值放到 l3 【3】的位置l3 和 l1 执行 --操作向前挪动一位l2 在原地保持不动
若是 l2 和 l1 所代表的值相等则任取一个
由此类推直到 num2 遍历完全部数组则跳出循环
此时还存在另外一种情况
num1
246 num2
135
通过上述操作我们可以推算出l1 先出了循环而 l2 此时还剩下一位此事的情况为
223456
此时 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
}
