資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究陣列中最大尺寸為 2，並且其總和小於給定值的最小劃分
問題陳述
給定一個正數陣列 arr[]，找出滿足以下屬性的陣列中的最小集合數：
- 一個集合最多包含兩個元素。這兩個元素無需連續。
- 集合中元素之和應小於或等於給定的鍵值。可以假設給定的鍵值大於或等於陣列中的最大元素。
示例
如果 arr[] = {1, 2, 3, 4}，k = 5，則可以建立以下 2 對：
{1, 4} 和 {2, 3}
演算法
- 對陣列進行排序
- 從已排序陣列的兩端開始，如果兩數之和小於或等於給定的鍵值，則將它們作為一個集合，否則僅考慮最後一個元素
示例
#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
int i, j;
sort (arr, arr + n);
for (i = 0, j = n - 1; i <= j; ++i) {
if (arr[i] + arr[j] <= key) {
--j;
}
}
return i;
}
int main() {
int arr[] = {1, 2, 3, 4};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
}輸出
編譯並執行以上程式時，將生成以下輸出：
Minimum set = 2
更新於：2019 年 11 月 22 日
69 次瀏覽
廣告