吉林大学学院网站建设群,郑州中原区建设局网站,wordpress站点自动推送,自己做网站教程一、合并两个有序数组 本题给出了两个整数数组nums1和nums2#xff0c;这两个数组均是非递减排列#xff0c;要求我们将这两个数组合并成一个非递减排列的数组。题目中还要求我们把合并完的数组存储在nums1中#xff0c;并且为了存储两个数组中全部的数据#xff0c;nums1中…一、合并两个有序数组 本题给出了两个整数数组nums1和nums2这两个数组均是非递减排列要求我们将这两个数组合并成一个非递减排列的数组。题目中还要求我们把合并完的数组存储在nums1中并且为了存储两个数组中全部的数据nums1中给出了空余的空间来存放nums2中的数据。本题的做法有很多在此我们主要讨论三种解题思路。
1.先合并后排序
我们可以先将nums2中的元素全部拷贝到nums1中的空闲空间中去然后再将nums1整体排序即可代码如下
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i m;int j 0;while(i m n) {nums1[i] nums2[j];}Arrays.sort(nums1);}
}2.正序双指针
我们可以先将nums1中的数据拷贝到一个新的数组nums3中去以便于我们对nums1本身的操作因为给出的两个数组是非递减排序的所以我们只要在遍历的过程中每次比较nums2和nums3中的元素将较小的那个元素放入nums1中即可具体代码如下
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] nums3 new int[m];//创建新数组来存放nums1中的数据for(int i 0; i m; i) {nums3[i] nums1[i];}int i 0;int o1 0;int o2 0;while(o1 m o2 n) {if(nums3[o1] nums2[o2]) {//挑选出较小的数据放入nums1然后对应的下标后移nums1[i] nums3[o1];} else {nums1[i] nums2[o2];}}while(o1 m) {//将剩余的数据全部放入nums1nums1[i] nums3[o1];}while(o2 n) {nums1[i] nums2[o2];}}
}3.倒序双指针
此为上一个解法的优化解法因为nums1中的数据存放在数组的前部分中后面为了给nums2中的数据留空间全部都是空的那我们就可以从后向前遍历这样就不需要创建新的数组来存放nums1中的数据了。只不过是我们需要每次选取nums1和nums2中较大的那个数据然后从后向前的存入nums1代码如下
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int index m n - 1;int i m - 1;int j n - 1;while(i 0 j 0) {if(nums1[i] nums2[j]) {nums1[index--] nums1[i--];} else {nums1[index--] nums2[j--];}}while(j 0) {nums1[index--] nums2[j--];}while(i 0) {nums1[index--] nums1[i--];}}
}
