Leecode 88.合并两个有序数组
2024-09-08 17:58:15
想法:
1:先把nums2中的所有元素都放到nums1,之后给合并后的数组排序
1 官方代码:
2 class Solution {
3 public void merge(int[] nums1, int m, int[] nums2, int n) {
4 for (int i = 0; i != n; ++i) {
5 nums1[m + i] = nums2[i];
6 }
7 Arrays.sort(nums1);
8 }
9 }
2:设两个数组的下标分别为i和j,当i不超过m且j不超过n时,比较nums1[i]和nums2[j],当nums1[i]大于nums2[j]时,挪动nums1中的元素,将nums2中的元素插入到此时i的位置,直到nums2指向的元素不大于nums1刚才指的元素tem
3:像之前给有序链表排序一样,建一个新的长度为m+n的数组,然后依次放元素进入新数组,之后将新数组复制到nums1中(这个方法是不是卡bug了)
1 官方代码:(居然认可了?这不是卡bug吗??那要限定nums1有啥意义)
2 class Solution {
3 public void merge(int[] nums1, int m, int[] nums2, int n) {
4 int p1 = 0, p2 = 0;
5 int[] sorted = new int[m + n];
6 int cur;
7 while (p1 < m || p2 < n) {
8 if (p1 == m) {
9 cur = nums2[p2++];
10 } else if (p2 == n) {
11 cur = nums1[p1++];
12 } else if (nums1[p1] < nums2[p2]) {
13 cur = nums1[p1++];
14 } else {
15 cur = nums2[p2++];
16 }
17 sorted[p1 + p2 - 1] = cur;
18 }
19 for (int i = 0; i != m + n; ++i) {
20 nums1[i] = sorted[i];
21 }
22 }
23 }
官方解法补充:双指针逆序
方法三:逆向双指针
上面创造临时变量新数组,是因为如果直接合并到数组nums1,nums1中的元素可能在取出之前被覆盖(os:把他移动就不会被覆盖了,不过复杂度提升了好多)。那么如何直接避免覆盖nums1中的元素呢?观察可知,nums1的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者中的较大者放进nums1的最后面。
1 class Solution {
2 public void merge(int[] nums1, int m, int[] nums2, int n) {
3 int p1 = m - 1, p2 = n - 1;
4 int tail = m + n - 1;
5 int cur;
6 while (p1 >= 0 || p2 >= 0) {
7 if (p1 == -1) {
8 cur = nums2[p2--];
9 } else if (p2 == -1) {
10 cur = nums1[p1--];
11 } else if (nums1[p1] > nums2[p2]) {
12 cur = nums1[p1--];
13 } else {
14 cur = nums2[p2--];
15 }
16 nums1[tail--] = cur;
17 }
18 }
19 }
最新文章
- [APUE]系统数据文件与信息
- 基础学习day11--多线程一线程的创建,运行,同步和锁
- JVM系列三:JVM参数设置、分析
- 70. Climbing Stairs
- IT书籍下载汇总--持续更新
- [jQuery] $.grep使用
- hdu 4911 Inversion(找到的倒数)
- Windows 2008 R2下 如何简单使用IIS来配置PHP网站
- 关于centOS 7的服务启动,端口查询,防火墙管理
- 小记:Touchpad 禁用和启用
- apache泛域名解析
- HBase 索引创建
- C# 使用SmtpClient发送Email
- Guitar Pro中如何添加与删除音轨
- neo4j通过LOAD CSV导入结点和关系
- Azure CosmosDB (4) 在一致性(Consistency)可用性(Availability)和性能(Performance)之间的权衡
- Game HDU - 3657(最小割)
- web前端开发面试题(答案)
- 表单控件 css的三中引入方式css选择器
- 本地管理表空间(LMT)与自动段空间管理(ASSM)概念