資料結構
網路
關係資料庫管理系統 (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
廣告