資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學陣列中K個最小和最大斐波那契數的和與積
在這個問題中，我們將找到陣列中K個最大和最小斐波那契數的和與積。
給定的問題非常基礎，旨在幫助初學者提高解決問題的能力。問題的目標是介紹如何從給定的元素陣列中篩選出斐波那契數，並計算最小和最大斐波那契數的和與積。
問題陳述
我們給定一個包含N個整數值的nums[]陣列。我們還給定一個正整數K。我們需要找到該陣列中K個最小和最大斐波那契元素的和與積。
注意 − 已知陣列始終包含至少K個斐波那契數。
示例
輸入
nums[] = {2, 1, 9, 55, 13, 68}; K = 3;
輸出
Minimum sum = 16 Minimum product = 26 Maximum sum = 70 Maximum product = 1430
解釋
給定陣列中的斐波那契數是[2, 1, 55, 13]。我們從這4個元素中取最小和最大的3個元素來計算和與積。
輸入
nums[] = {3, 13, 21, 55, 34, 89, 144, 233}; K = 2;
輸出
Minimum sum = 16 Minimum product = 39 Maximum sum = 377 Maximum product = 33552
解釋
給定陣列的所有元素都是斐波那契數。因此，最小的2個元素是[3, 13]，最大的4個元素是[233, 144]。
方法
在這種方法中，我們將找到陣列的最大元素。之後，我們將找到1到最大元素範圍內所有斐波那契數。
接下來，我們將使用兩個優先順序佇列來儲存所有斐波那契數。一個優先順序佇列將使用最大堆來按降序儲存數字，另一個將使用最小堆來按升序儲存數字。之後，我們可以從佇列中取出前K個元素並進行加法或乘法運算。
演算法
步驟1 − 從陣列元素中獲取最大元素。
步驟2 − 定義名為fibSet的集合，並將其作為getFibs()函式的引數傳遞，以獲取1到最大元素範圍內所有斐波那契數。
步驟2.1 − 在getFibs()函式中，分別用0和1初始化left和right變數。並將它們插入到fibSet集合中。
步驟2.3 − 當'right'變數的值小於'maxEle'值時進行迭代。
步驟2.4 − 將left + right儲存到temp中。並將'temp'值插入到集合中。
步驟2.5 − 將left更新為right，並將right更新為temp值。
步驟3 − 現在，建立最小斐波那契數min_fib和最大斐波那契數max_fib優先順序佇列。min_fib應該使用最小堆，max_fib應該使用最大堆（預設）。
步驟4 − 現在，將fibSet集合的所有元素插入到min_fib和max_fib佇列中。
步驟5 − 用1初始化min_p和max_p來儲存K個最小和最大斐波那契元素的積。並用0初始化min_s和max_s來儲存K個最小和最大斐波那契元素的和。
步驟6 − 從兩個佇列中提取前K個元素，並將它們相加和相乘。
步驟7 − 列印結果值。
示例
#include <bits/stdc++.h>
using namespace std;
void getFibs(set<int> &fibSet, int maxEle) {
// 0 and 1 is Fibonacci number
int left = 0, right = 1;
fibSet.insert(left);
fibSet.insert(right);
// Find Fibbonacci numbers
while (right <= maxEle) {
int temp = right + left;
fibSet.insert(temp);
left = right;
right = temp;
}
}
void findSumAndProduct(int nums[], int n, int k) {
// Get the maximum element of the array
int maxEle = *max_element(nums, nums + n);
// Get all Fibonacci numbers in the range of 1 to maxEle
set<int> fibSet;
getFibs(fibSet, maxEle);
// Max and min heap to store fibonacci numbers
priority_queue<int> max_fib;
priority_queue<int, vector<int>, greater<int>> min_fib;
// Insert fibonacci numbers into heaps
for (int p = 0; p < n; p++) {
if (fibSet.find(nums[p]) != fibSet.end()) {
min_fib.push(nums[p]);
max_fib.push(nums[p]);
}
}
long long int min_p = 1, max_p = 1, min_s = 0, max_s = 0;
// Get first K elements from min and max heap
while (k--) {
// For products
min_p *= min_fib.top();
max_p *= max_fib.top();
// For sum
min_s += min_fib.top();
max_s += max_fib.top();
// Rremove front elements from queue
min_fib.pop();
max_fib.pop();
}
cout << "The sum of K minimum fibonacci elements is " << min_s << "\n";
cout << "The product of K minimum fibonacci elements is " << min_p << "\n";
cout << "The sum of K maximum fibonacci elements is " << max_s << "\n";
cout << "The product of K maximum fibonacci elements is " << max_p;
}
int main() {
int nums[] = {2, 1, 9, 55, 13, 68};
int N = sizeof(nums) / sizeof(nums[0]);
int K = 3;
findSumAndProduct(nums, N, K);
return 0;
}
輸出
The sum of K minimum fibonacci elements is 16 The product of K minimum fibonacci elements is 26 The sum of K maximum fibonacci elements is 70 The product of K maximum fibonacci elements is 1430
時間複雜度 − O(NLogN) 用於將元素插入佇列。
空間複雜度 − O(N) 用於在集合中儲存斐波那契數。
結論
這個問題介紹了兩個基本概念。一個是找到給定範圍內的斐波那契數，另一個是使用優先順序佇列。每當我們需要在N個元素中找到最小或最大的K個元素時，都應該使用優先順序佇列。但是，我們也可以透過對陣列進行排序來達到相同的結果。
瀏覽量：119
