您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
合并两个有序数组(图文)
第十三双眼睛2023-11-25【数据结构与算法】人已围观
简介合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
第一种方法是:先将数组2合并到数组1中1去,然后对数组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:
很赞哦! ()