【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)
-
作者主页: 🔗进朱者赤的博客
(图片来源网络,侵删) -
精选专栏:🔗经典算法
-
作者简介:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名)
-
❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论,💬支持博主,记得点个大大的关注,持续更新🤞
————————————————-
目录
- 题目描述
- 思路及实现
- 方式一:从后向前双指针
- 思路
- 代码实现
- Java版本
- C语言版本
- Python3版本
- 复杂度分析
- 方式二:从前往后双指针(需要额外空间)
- 思路
- 代码实现
- Java版本
- C语言版本
- Python3版本
- 复杂度分析
- 总结
- 相似题目
- 标签(题目类型):数组,双指针
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。 示例 1: 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。 示例 2: 输入:nums1 = [1], m = 1, nums2 = [], n = 0 输出:[1] 解释:需要合并 [1] 和 [] 。 合并结果是 [1] 。 示例 3: 输入:nums1 = [0], m = 0, nums2 = [1], n = 1 输出:[1] 解释:需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 提示: nums1.length == m + n nums2.length == n 0 int i = m - 1; // nums1 有效元素末尾指针 int j = n - 1; // nums2 末尾指针 int k = m + n - 1; // 合并后数组末尾指针 while (j = 0) { if (i = 0 && nums1[i] nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } } int i = m - 1; int j = n - 1; int k = m + n - 1; while (j = 0) { if (i = 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } }
说明:
- C语言版本的实现与 Java 版本类似,只是参数传递和数组访问的方式略有不同。
Python3版本
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None: i = m - 1 j = n - 1 k = m + n - 1 while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1
说明:
- Python 版本的实现逻辑与 Java 和 C 版本相同,只是语法上有些差异。
复杂度分析
- 时间复杂度:O(m + n),其中 m 和 n 分别是 nums1 和 nums2 的长度。需要遍历两个数组中的所有元素。
- 空间复杂度:O(1),除了原数组 nums1 外,没有使用额外的空间。
方式二:从前往后双指针(需要额外空间)
思路
我们创建一个新的数组 temp,其长度为 m + n(即 nums1 和 nums2 合并后的长度)。然后,我们使用两个指针分别遍历 nums1 和 nums2,将较小的元素依次放入 temp 数组中,直到其中一个数组遍历完。最后,将另一个数组中剩余的元素(如果有的话)直接复制到 temp 数组的末尾。最后,将 temp 数组的内容复制回 nums1。
代码实现
Java版本
public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp = new int[m + n]; int i = 0, j = 0, k = 0; while (i
- Python 版本的实现逻辑与 Java 和 C 版本相同,只是语法上有些差异。
- C语言版本的实现与 Java 版本类似,只是参数传递和数组访问的方式略有不同。
- 标签(题目类型):数组,双指针
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。