合并两个有序数组
数组 两个 合并 有序
2023-09-14 09:02:34 时间
自己的写法:对较长的nums1数组使用了双指针法,qp一个在前一个在后,初始时分别指向nums1的第一个元素和第二个元素,分情况讨论有三种,如下代码所示:
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
//双指针
int q = 0;
int p = 1;
for (int i = 0; i < n; i++)
{
q = 0;
p = 1;
//一共三种情况
//1.插在数组第一个元素前面
if (nums2[i] <=nums1[0])
{
for (int j = m-1; j >= 0; j--)
{
nums1[j + 1] = nums1[j];
}
nums1[0] = nums2[i];
m++;
continue;
}
//2.插在数组最后一个元素的后一个位置
if (nums2[i] >= nums1[m - 1])
{
nums1[m] = nums2[i];
m++;
continue;
}
//3.插在快慢指针qp之间
while (p < m)
{
if (nums2[i] <= nums1[p] && nums2[i] > nums1[q])
{
for (int j = m - 1; j >= p; j--)
{
nums1[j + 1] = nums1[j];
}
nums1[q + 1] = nums2[i];
m++;
break;
}
q++, p++;
}
}
}
};
void test()
{
vector<int> v1 = { 1,2,3,0,0,0 };
vector<int> v2 = { 2,5,6 };
Solution s;
s.merge(v1, 3, v2, 3);
for (int i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
}
int main()
{
test();
system("pause");
return 0;
}
参照他人的解法
方法一 : 合并后排序
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
//第一步合并两个容器
int j = 0;
for (int i = m; i < m + n; i++)
{
nums1[i] = nums2[j++];
}
//对合并后的容器进行排序
sort(nums1.begin(), nums1.end());
}
};
方法三 : 双指针 / 从后往前
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
int i = m + n - 1;
m--, n--;
while (n >= 0)
{
while (m >= 0 && (nums1[m] > nums2[n]))
{
nums1[i--] = nums1[m--];
}
nums1[i--] = nums2[n--];
}
}
};
相关文章
- 两个数组拼接
- 2022-09-13:给你两个整数 m 和 n ,分别表示一块矩形木块的高和宽。 同时给你一个二维整数数组 prices ,其中 prices[i] = [hi
- 88. 合并两个有序数组
- JS面试题-类数组转数组方法
- JavaScript数组splice方法
- 【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
- 2023-03-02:给定一个数组arr,长度为n, 任意相邻的两个数里面至少要有一个被选出来,组成子序列,才是合法的! 求所有可能的合法子序列中,最大中位数是
- js比较前后两个数组对象的差异
- 【C 语言】数组 ( 多维数组做函数形参退化为指针过程 | int array[2][3] -> int array[][3] -> int (*array)[3] )
- LeetCode每日一题:合并两个有序数组
- 力扣——寻找两个正序数组的中位数
- PHP list():把数组中的值赋给一组变量
- JS取两个数组相同的元素详解编程语言
- C语言之二维数组详解编程语言
- Oracle中数组技术有助于提高系统性能(oracle中数组的应用)
- PHP合并两个数组的两种方式的异同
- C++用指针变量作为函数的参数接受数组的值的问题详细总结
- 浅谈Go语言中字符串和数组