数据结构
网络
关系数据库管理系统 (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
