C++算法：合并两个有序数组并求中位数 |21xrx.com

C++算法：合并两个有序数组并求中位数

2023-07-05 02:53:06 深夜i -- --

C++ 算法合并有序数组中位数

合并两个有序数组并求中位数是一个常见的算法问题。在这个问题中，我们有两个已经排好序的数组，我们需要将它们合并成一个有序的数组，并找到这个新数组的中位数。

这个问题看起来挺困难，但是在C++中实现起来非常简单。下面是一个基于C++的算法实现合并两个有序数组并求中位数的例子：


#include <iostream>
#include <vector>
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
  int m = nums1.size();
  int n = nums2.size();
  int i = 0, j = 0;
  std::vector<int> sorted;
  while (i < m && j < n) {
    if (nums1[i] < nums2[j]) {
      sorted.push_back(nums1[i]);
      i++;
    }
    else {
      sorted.push_back(nums2[j]);
      j++;
    }
  }
  while (i < m) {
    sorted.push_back(nums1[i]);
    i++;
  }
  while (j < n) {
    sorted.push_back(nums2[j]);
    j++;
  }
  int size = sorted.size();
  if (size % 2 == 0) {
    return ((double)sorted[size / 2] + (double)sorted[size / 2 - 1]) / 2;
  }
  else {
    return (double)sorted[size / 2];
  }
}
int main() {
  std::vector<int> nums1 = 1;
  std::vector<int> nums2 = 10;
  double result = findMedianSortedArrays(nums1, nums2);
  std::cout << "The median is " << result << std::endl;
  return 0;
}

上面的代码首先定义了一个函数`findMedianSortedArrays`来合并两个有序数组并求中位数。其中，算法的核心部分是一个归并排序的过程。我们定义两个指针i和j分别指向两个数组的头部，然后比较它们的值，将较小的值添加到新的数组中，然后将指针向右移动一位。重复这个过程，直到达到了数组的末尾。

如果新数组的长度是偶数，那么我们需要找到两个中间值，将它们相加后除以二，否则我们直接返回中间值就可以了。

最后，在main函数中，我们定义了两个数组，然后调用上面定义的函数来找到这两个数组的中位数。

总结

在C++中实现合并两个有序数组并求中位数的算法，只需要使用归并排序的思路即可。这种算法非常高效，而且易于理解和实现。如果你正在学习C++编程，这个例子应该可以帮助你更好地理解算法和向量的使用。

上一篇: idea打包java可执行jar包

下一篇: "C++编写烟花效果的程序代码"

评论区

()

相似文章