写出合并两个有序数组的代码
时间: 2023-09-10 21:06:19 浏览: 48
可以参考如下的Python代码实现:
```python
def merge_sorted_array(nums1, m, nums2, n):
i, j, k = m-1, n-1, m+n-1
while i >= 0 and j >= 0:
if nums1[i] >= nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
k -= 1
j -= 1
```
其中,nums1和nums2分别为两个已经有序的数组,m和n分别是它们的长度,函数的作用是将两个数组合并成一个有序数组nums1。这个函数的基本思路是借助三个指针i、j和k,分别指向nums1、nums2和合并后的数组nums1,然后从后往前遍历两个数组,比较它们的末尾元素大小,将较大的元素放到nums1的最后,直到其中一个数组遍历完毕,然后再将另一个数组的元素全部复制到nums1中。这样就能得到合并后的有序数组了。
相关问题
python写寻找两个正序数组的中位数
题目描述:
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:
输入:nums1 = [,], nums2 = [,]
输出:.00000
示例 4:
输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
nums1.length == m
nums2.length == n
<= m <= 100
<= n <= 100
1 <= m + n <= 200
-106 <= nums1[i], nums2[i] <= 106
解题思路:
首先,我们需要将两个数组合并成一个有序数组,然后再根据数组长度的奇偶性来计算中位数。
对于合并两个有序数组,我们可以使用双指针的方法,从头开始遍历两个数组,每次将较小的数放入新的数组中,直到其中一个数组遍历完毕,然后将另一个数组中剩余的数全部放入新的数组中。
对于计算中位数,我们需要分为两种情况:
当数组长度为奇数时,中位数为新数组的中间数。
当数组长度为偶数时,中位数为新数组的中间两个数的平均数。
代码实现:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 合并两个有序数组
nums = []
i, j = ,
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
nums.append(nums1[i])
i += 1
else:
nums.append(nums2[j])
j += 1
if i < len(nums1):
nums += nums1[i:]
if j < len(nums2):
nums += nums2[j:]
# 计算中位数
n = len(nums)
if n % 2 == :
return (nums[n//2-1] + nums[n//2]) / 2
else:
return nums[n//2]
写出合并排序的C语言伪代码
以下是合并排序的C语言伪代码:
```
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
```
在上述伪代码中,`merge_sort`函数将数组分成两半,直到每个部分只有一个元素。然后,`merge`函数将两个有序数组合并为一个有序数组。最终,`merge_sort`函数将这些有序的部分合并成一个完全有序的数组。