C++ 数组中的最小k个和最大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 - 将min_p和max_p初始化为1，用于存储K个最小和最大斐波那契元素的乘积。还将min_s和max_s初始化为0，用于存储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