数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学给定数组和k，求|ai + aj – k|的最小可能值 (C++)
问题陈述
给定一个包含n个整数的数组和一个整数K。找到所有无序对{i, j}的总数，使得|ai + aj – k|的绝对值最小，其中i != j。
示例
如果arr[ ] = {0, 4, 6, 2, 4} 且k = 7，那么我们可以创建以下5对，最小值为1
{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}
算法
遍历所有可能的对，对于每一对，我们将检查(ai + aj – K)的值是否小于我们当前的最小值。根据上述条件的结果，我们共有三种情况：
- abs( ai + aj – K) > 最小值 - 不做任何操作，因为这对不会计入最小可能值。
- abs(ai + aj – K) = 最小值 - 增加导致最小可能值的配对计数。
- abs( ai + aj – K) < 最小值 - 更新最小值并将计数设置为1。
示例
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getPairs(int *arr, int n, int k) {
int minValue = INT_MAX;
int pairs = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int val = abs(arr[i] + arr[j] - k); if (val < minValue) {
minValue = val;
pairs = 1;
} else if (val == minValue) {
++pairs;
}
}
}
cout << "Min value = " << minValue << endl; cout << "Total pairs = " << pairs << endl;
}
int main() {
int arr[] = {0, 4, 6, 2, 4};
int k = 7;
int n = sizeof(arr) / sizeof(arr[0]);
getPairs(arr, n, k);
return 0;
}输出
编译并执行上述程序后，将生成以下输出：
Min value= 1 Total pairs = 5
更新于：2019年11月22日
浏览量：188
广告