C++ 中计算数组中绝对差不大于 K 的最大元素个数

给定一个数组，假设为 arr[]，包含任意大小的整数元素，以及一个正整数 k，任务是计算那些绝对差不大于给定整数 k 的元素对的个数。

数组是一种数据结构，可以存储相同类型元素的固定大小的顺序集合。数组用于存储数据集合，但通常将数组视为相同类型变量的集合更有用。

例如

Input − int arr[] = {2, 3, 6, 12, 14}, k= 5
Output − count is : 3

说明 - 最大绝对差不大于 k（在本例中为 5）的配对，形成的配对为：(2, 3), (2, 6), (3,6)，即 {2, 3, 6}，因此计数为 3。

Input − int arr[] = {2, 3, 6, 12, 14}, k= 10
Output − count is : 4

说明 - 最大绝对差不大于 k（在本例中为 10）的配对，形成的配对为：(2, 3), (2, 6), (3,6), (2, 12), (3, 12), (6, 12)，即 {2, 3, 6, 12}，因此计数为 4，因为最大元素为 4。

Input − int arr[] = {2, 3, 6, 12, 14}, k= 0
Output − count is : 0

说明 - 由于没有差为 0 的配对，因此计数为 0。

下面程序中使用的方法如下

  • 创建一个数组，假设为 arr[]，以及一个正整数 k

  • 使用 length() 函数计算数组的长度，该函数将根据数组中的元素返回一个整数值。

  • 取一个临时变量来存储元素的计数。

  • 声明两个临时变量，假设为 first 和 last，并初始化为 0

  • 调用 sort 方法对数组进行排序，并将数组和数组的大小作为参数传递给函数。

  • 开始循环，从 i 为 0 开始，到 i 小于数组的大小。

  • 在循环内部，开始 while 循环，j<size 并且 arr[j] <= arr[i] + k

  • 在 while 循环内部，检查 IF count < j-i，则将 count 设置为 j - i，并将 first 设置为 i，last 设置为 j

  • 返回计数

  • 打印结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

 在线演示

#include <iostream>
#include <algorithm>
using namespace std;
int countmax(int arr[], int size, int K){
   int result = 0;
   int i = 0, j = 0;
   int beg = 0;
   int end = 0;
   // Sort the array
   sort(arr, arr + size);
   // Find max elements
   for (i = 0; i < size; i++) {
      // Count all elements which are in the range
      while (j < size && arr[j] <= arr[i] + K)
      j++;
      if (result < (j - i)) {
         result = (j - i);
         beg = i;
         end = j;
      }
   }
   // Return the max count
   return result;
}
// main function
int main(){
   int arr[] = { 2, 3, 6, 12, 14 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int K = 5;
   cout <<"count is "<<countmax(arr, size, K) << endl;
   return 0;
}

输出

如果运行以上代码，将得到以下输出：

count is 3

更新于: 2020年5月15日

478 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告