C++如何在数组中查找与M最接近的数？ |21xrx.com

C++如何在数组中查找与M最接近的数？

2023-07-05 02:36:33 深夜i -- --

C++ 数组查找最接近 M

C++是一种重要的编程语言，它在处理数据时有着广泛的应用。在数组中查找与M最接近的数，是C++程序员经常遇到的问题之一。本文将介绍一些可行的解决方案。

方法一：暴力枚举

暴力枚举是最基本的方法，对于小规模的数据可以使用。具体实现步骤为：循环遍历整个数组，计算每个元素与M的差值，找到差值最小的元素，即为与M最接近的数。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。

代码如下：


int findClosest(int arr[], int n, int M)
{
  int minDiff = abs(arr[0] - M);
  int closest = arr[0];
  for (int i = 1; i < n; i++) {
    int diff = abs(arr[i] - M);
    if (diff < minDiff) {
      minDiff = diff;
      closest = arr[i];
    }
  }
  return closest;
}

方法二：二分查找

二分查找是一种高效的算法，适用于已排序的数组。具体实现步骤为：利用二分查找方法，找到M在数组中的位置p，再从p开始向左和向右分别搜索与M相邻的元素，比较它们与M的差值大小，找到差值最小的元素，即为与M最接近的数。这种方法的时间复杂度为O(logn)，空间复杂度为O(1)。

代码如下：


int findClosest(int arr[], int n, int M)
{
  int l = 0, r = n - 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (arr[mid] == M) return arr[mid];
    else if (arr[mid] > M) r = mid - 1;
    else l = mid + 1;
  }
  int left = abs(arr[l - 1] - M);
  int right = abs(arr[l] - M);
  return (left <= right) ? arr[l - 1] : arr[l];
}

方法三：双指针法

双指针法也是一种高效的算法，适用于已排序的数组。具体实现步骤为：让两个指针l和r分别指向数组的首位，每次计算arr[l]和arr[r]与M的差值大小，将当前差值较小的指针向中间移动，直到l>=r为止。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。

代码如下：


int findClosest(int arr[], int n, int M)
{
  int l = 0, r = n - 1;
  while (l < r) {
    if (abs(arr[l] - M) <= abs(arr[r] - M)) r--;
    else l++;
  }
  return arr[l];
}

以上就是三种在数组中查找与M最接近的数的方法。针对不同的数据规模和数据特征，我们可以选择不同的算法来解决问题。在实际运用中，我们应该综合考虑时间复杂度和空间复杂度，选择最合适的算法来解决问题。

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

下一篇: 实现的渐进式JavaScript框架-Vue

评论区

()

相似文章