您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

合并两个有序数组(图文)

第十三双眼睛2023-11-25【数据结构与算法】人已围观

简介合并两个有序数组
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

第一种方法是：先将数组2合并到数组1中1去，然后对数组1进行排序。代码如下：

public static void method1(int[] nums1, int m, int[] nums2, int n) {
   int index = 0;
   for (int i = m; i < nums1.length; i++) {
       nums1[i] = nums2[index];
       index ++;
   }
   Arrays.sort(nums1);
}

第二种方法，另外创建一个数组，作为数组1的备份，遍历两个数组，将两个数组中的元素进行比较，将小的元素放到数组1中去。

public static void method2(int[] nums1, int m, int[] nums2, int n) {
   int[] nums1copy = Arrays.copyOf(nums1,nums1.length);
   int i = 0;
   int j = 0;
   int k = 0;
   while (true) {
       if (i >= m || j >= n) {
           break;
       }
       if (nums1copy[i] <= nums2[j]) {
           nums1[k] = nums1copy[i];
           i ++;
       } else {
           nums1[k] = nums2[j];
           j ++;
       }
       k ++;
   }
   if (i >= m) {
       for (; k < nums1.length; k ++) {
           nums1[k] = nums2[j];
           j ++;
       }
   }
   if (j >= n) {
       for (; k < nums1.length; k ++) {
           nums1[k] = nums1copy[i];
           i ++;
       }
   }
}

最后一种方法，就是，从后向前遍历两个数组，挨个比较，将大的元素放到数组的末尾。代码如下：

public static void method3(int[] nums1, int m, int[] nums2, int n) {
   int i = m-1;
   int j = n-1;
   int k = nums1.length - 1;
   while (true) {
       if (i < 0 || j < 0) {
           break;
       }
       if (nums1[i] >= nums2[j]) {
           nums1[k] = nums1[i];
           i --;
       } else {
           nums1[k] = nums2[j];
           j --;
       }
       k --;
   }
}

Tags：

很赞哦！ ()

上一篇：加1(图文)

下一篇：二进制求和