超市网站开发建设建议,共享影院 wordpress,网线制作步骤图片,网站建设承诺文章来源#xff1a; https://blog.csdn.net/weixin_45630258/article/details/132738318 欢迎各位大佬指点、三连 一、数组的合并–双指针[快慢指针]
1、题目#xff1a;
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0…文章来源 https://blog.csdn.net/weixin_45630258/article/details/132738318 欢迎各位大佬指点、三连 一、数组的合并–双指针[快慢指针]
1、题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
2、分析特点
两个数组已经被排序相当于两条有序的队列非递减从小到大排队每次都从两条队伍中取走最小的那个数放到结果中。
3、代码
4、复杂度分析 时间复杂度O(mn)O(mn)O(mn)。 指针移动单调递增最多移动 mnmnmn 次因此时间复杂度为 O(mn)O(mn)O(mn)。 空间复杂度O(mn)O(mn)O(mn)。 需要建立长度为 mnmnmn 的中间数组 sorted。 5、总结
本题比较简单只需要抓住有序递增的两个数组直接当队列抓最小。当然更简单的是直接把其中一个数组的全部元素存储到另外一个数组后面的空间然后利用封装好的方法排序即可即 Arrays.sort() 方法 二、数组的删除–双指针[快慢指针]
1、题目
给你一个数组 nums和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
2、分析特点
题目要求原地移除移除所有val的元素则 结果数组一定比原数组的长度更短。要求原地移除 我们可以把结果数组直接写在原数组上并且结果数组是那些非等于val的元素组成的从位置0开始到某个位置作为结果数组而原数组需要从0开始到整个数组的长度进行遍历 使用双指针。结果数组的指针[0, left] 结果数组的目的是收集起来结果他是left一步步进行加加的。原数组的指针[0, right]right 原数组长度right 是用于指向原数组当前的元素是否不会等于val可以被收集。
3、代码
4、复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 为序列的长度。我们只需要遍历该序列至多两次。 空间复杂度O(1)O(1)O(1)。我们只需要常数的空间保存若干变量。 5、总结
本题比较简单只需要抓住题意要求原地移除原地结果只能输出到原数组上面移除则结果数组长度比原数组更短。利用结果数组从0开始left进行收集而原数组使用right指针从0开始遍历判断当前元素是否可以被收集起来。 目的就是收集所有符合条件的元素。 三、数组的轮询–取模
1、题目
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
2、分析特点 轮转 取模运算 我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度我们遍历原数组将原数组下标为 i 的元素放至新数组下标为 (ik) mod n 的位置最后将新数组拷贝至原数组即可。
3、代码
4、复杂度分析 时间复杂度 O(n)其中 n 为数组的长度。空间复杂度 O(n)。 5、总结
轮转、循环 k 步要想到取模运算另外需要一个新数组作为结果数组是因为如果我们不使用额外数组我们直接将每个数字放至它最后的位置这样被放置位置的元素会被覆盖从而丢失所以需要一个新数组作为结果数组最后拷贝回去原数组。 四、数组的最大差值–打擂台法
1、题目
给定一个整数数组 nums找出给定数组中两个数字之间的最大差值。要求第二个数字必须大于第一个数字。
2、分析特点
求最大差值 最大值 - 最小值只需要遍历价格数组一遍记录历史最小值非最小值的考虑是最大值。
3、代码
4、复杂度分析 时间复杂度O(n)只需要遍历一次。空间复杂度O(1)只使用了常数个变量。 5、总结
使用打擂台的思想遍历的时候考虑当前值是最小值则记录最小值否则考虑当前值是最大值进行更新。 如果本文对你有帮助的话记得给一乐点个赞哦感谢
