Java算法题-解析 "合并有序数组" 算法问题

题目:
给定两个有序整数数组 nums1
和 nums2
,将 nums2
合并到 nums1
中,使得 nums1
成为一个有序数组。
引言:
"合并有序数组" 是一个关于数组操作的问题。解决这个问题需要对数组的操作和归并的思路有一定的理解,同时需要找到一种方法来将两个有序数组合并。通过解答这个问题,我们可以提升对数组操作和归并的考虑,同时也能拓展对问题求解的能力。
算法思路:
为了将两个有序数组合并成一个有序数组,我们可以从数组的尾部开始比较,并将较大的元素逐步放置在 nums1
数组的末尾。具体思路如下:
- 初始化两个指针,分别指向
nums1
和nums2
数组的有效元素的末尾位置。 - 初始化一个指针,指向
nums1
数组的最后一个位置,用于存放合并后的元素。 - 从后向前遍历,比较
nums1
和nums2
数组的元素,将较大的元素放置在nums1
的末尾,然后将相应的指针向前移动。 - 当其中一个数组遍历完后,将剩余的元素依次放置在
nums1
的前面。
代码实现:
以下是使用 Java 实现的 "合并有序数组" 算法的示例代码:
public class MergeSortedArray {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] >= nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
}
}
算法分析:
- 时间复杂度:遍历两个数组中的每个元素一次,所以时间复杂度为 O(m + n),其中 m 和 n 分别是
nums1
和nums2
的长度。 - 空间复杂度:只使用了常数级别的额外空间,所以空间复杂度为 O(1)。
示例和测试:
假设给定数组 nums1 = [1,2,3,0,0,0]
,m = 3
,以及数组 nums2 = [2,5,6]
,n = 3
。根据算法,合并后的有序数组为 [1,2,2,3,5,6]
。
我们可以使用以下代码进行测试:
public class Main {
public static void main(String[] args) {
MergeSortedArray solution = new MergeSortedArray();
int[] nums1 = {1, 2, 3, 0, 0, 0};
int m = 3;
int[] nums2 = {2, 5, 6};
int n = 3;
solution.merge(nums1, m, nums2, n);
System.out.print("Merged sorted array: ");
for (int num : nums1) {
System.out.print(num + " ");
}
}
}
总结:
"合并有序数组" 算法题要求将两个有序数组合并成一个有序数组,是一个关于数组操作和归并的问题。通过实现这个算法,我们可以提升对数组操作和归并的考虑,同时也能拓展对问题求解的能力。这个问题通过从数组的尾部开始比较,逐步将较大的元素放置在一个数组的末尾,强调了如何将两个有序数组合并。