当前位置:网站首页>Combining two ordered arrays
Combining two ordered arrays
2022-08-01 19:03:00 【Lanzhou Qianfan】
Combining two ordered arrays
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目.
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列.
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略.nums2 的长度为 n .
The first is a violent solution
We can merge the two arrays directly,然后直接排序
Start directly after the significant bit of the arraynum2The array element assignment of ,Then, after the two are merged, they are sorted together using the data sorting method.The underlying principle is a quick sort.
for (int i = 0; i < nums2.length; i++) {
nums1[m++]=nums2[i];
}
Arrays.sort(nums1);
One disadvantage of doing this is that,Both arrays we are given are sorted arrays,But if we re-merge and re-sort,Disrupted again,Does not take advantage of the ordered nature of the original unmerged array.
So we propose a new approach.如下,We define two indexes,Actually you can think of it as a moving pointer,数组1,2are given respectivelynums1,nums2,Then we define a temporary array.The size of the temporary array is equal to num1
So what do you do when you are ready?First of all, the initial words pointed to by the two pointers of the first array and the second array are the head of the array.比较开始,If the first pointer points to the value of the element at the head index of the array is greater than the second head,Then we give the elements of the second head of the array to the head of the temporary array.Otherwise, it is given to array one,It can be given to any array if it is equal.
Moves the pointer to the corresponding array backwards when given,如下.When equal, we can give either one
You see this is a sorted result,Finally, we reassign the element values of the temporary array to num1.Because the title requires itnum1.
到了这一步的时候,我们的3Temporary array is also given,At this time, the following elements are not valid,所以我们就直接将num2The remaining elements are given to a temporary array
实现代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int nums3[] = new int[m+n];
for (int i = 0; i < nums3.length; i++) {
if(pre01>=m)
{
nums3[i]= nums2[pre02++];
}
else if (pre02>=n)
{
nums3[i]= nums1[pre01++];
}
else if (nums1[pre01]>=nums2[pre02])
{
nums3[i]=nums2[pre02++];
}else if (nums1[pre01]<nums2[pre02])
{
nums3[i]=nums1[pre01++];
}
}
for (int i = 0; i < nums1.length; i++) {
nums1[i]=nums3[i];
}
}
Another is that we don't have to do a temporary array,因为num1The back of the array was originally reserved for space.When comparing, we can compare in reverse order,That is to say, the comparison starts from the drunken element of the two,Elements are placed largenum1后面,Add in order from back to front.
Initially both pointers are tailed.然后开始比较.
Then go on like this
到这里呢,如果nums1If the element is larger,We'll move it back.
Then the smaller one will replace the element in its original position,In fact, after a lot of comparisons,You will find the end condition situationnum2There we use the pointer to point to the back of the head,When the comparison is done and then return to the loop,Determine whether the next move of the pointer is less than the index1,小于1就break;结束掉.
当然如果nums1A lot of elements are relatively large,It is likely that it has finished traversing first,那么这样的话,We'll take it straight to usnums2The elements are given in ordernums11前面.That's how it's sorted.
int nums3[] = new int[m+n];
// for (int i = 0; i < nums2.length; i++) {
// nums1[m++]=nums2[i];
// }
// Arrays.sort(nums1);
// for (int i : nums1) {
// System.out.println(i);
// }
int pre01 =m-1,pre02 =n-1;
for (int i =m+n-1; i >=0; i--) {
if (pre01<0)
{
nums1[i]=nums2[pre02--];
}
else if (pre02<0)
{
break;
}else if (nums1[pre01]>nums2[pre02])
{
nums1[i]= nums1[pre01--];
}
else{
nums1[i]= nums2[pre02--];
}
}
Compare these three approaches,The first is more time-consuming,Because there is a shuffled reordering,The latter two use pointer-like move index comparisons,The order of the original array is not disrupted,效率都非常高,But the third is not using a temporary array,Therefore, the space complexity of the third type is relatively low,占用内存少.
边栏推荐
- MySQL中超键、主键及候选键的区别是什么
- 力扣刷题之移动零
- The XML configuration
- 【蓝桥杯选拔赛真题47】Scratch潜艇游戏 少儿编程scratch蓝桥杯选拔赛真题讲解
- To drive efficient upstream and downstream collaboration, how can cross-border B2B e-commerce platforms release the core value of the LED industry supply chain?
- 使用常见问题解答软件的好处有哪些?
- 日志工厂(详细)
- 升哲科技携全域数字化方案亮相2022全球数字经济大会
- MLX90640 Infrared Thermal Imager Temperature Measurement Module Development Notes (Complete)
- 硬件大熊原创合集(2022/07更新)
猜你喜欢
Three solutions: npm WARN config global --global, --local are deprecated. Use --location=global instead.
三种方案解决:npm WARN config global --global, --local are deprecated. Use --location=global instead.
LeetCode 0152. Product Maximum Subarray: dp + Roll in Place
How many steps does it take to convert an ENS domain name into music?
[pyqt5] Custom controls to achieve scaling sub-controls that maintain the aspect ratio
Redis启动时提示Creating Server TCP listening socket *:6379: bind: No error
Try compiling QT test on Allwinner V853 development board
Win11如何开启剪贴板自动复制?Win11开启剪贴板自动复制的方法
Win11怎么安装语音包?Win11语音包安装教程
【木棉花】#夏日挑战赛# 鸿蒙小游戏项目——数独Sudoku(3)
随机推荐
123123123123
【综述专栏】IJCAI 2022 | 图结构学习最新综述:研究进展与未来展望
How to install voice pack in Win11?Win11 Voice Pack Installation Tutorial
Multi-Party Threshold Private Set Intersection with Sublinear Communication-2021: Interpretation
The elder brother of the goldfish RHCA memoirs: CL210 experiment management it network - chapter
LeetCode 0152. Product Maximum Subarray: dp + Roll in Place
Goldfish Brother RHCA Memoirs: CL210 manages OPENSTACK network -- network configuration options
[Neural Network] This article will take you to easily analyze the neural network (with an example of spoofing your girlfriend)
In the background of the GBase 8c database, what command is used to perform the master-slave switchover operation for the gtm and dn nodes?
Live chat system technology (8) : vivo live IM message module architecture practice in the system
Tencent Cloud Hosting Security x Lightweight Application Server | Powerful Joint Hosting Security Pratt & Whitney Version Released
Multi-Party Threshold Private Set Intersection with Sublinear Communication-2021:解读
Win11校园网无法连接怎么办?Win11连接不到校园网的解决方法
483-82 (23, 239, 450, 113)
Try compiling QT test on Allwinner V853 development board
哈哈!一个 print 函数,还挺会玩啊!
ClassID的计算中,&表示啥意思
explain 各字段介绍
483-82(23、239、450、113)
SaaS管理系统的应用优势在哪里?如何高效提升食品制造业数智化发展水平?