数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学寻找最大的 3 的倍数（使用队列）
在这个问题中，我们将使用数组元素找到最大的 3 的倍数。
简单的方法是生成数组元素的所有可能组合，并检查它是否能被 3 整除。通过这种方式，跟踪最大的 3 的倍数。
高效的方法是使用三个队列。我们可以使用队列根据除以 3 后的余数存储元素。之后，我们可以从队列中移除一些元素，以从剩余的数组元素中构成一个 3 的倍数。
问题陈述 - 我们给定一个包含 N 个正整数元素的数组。我们需要使用数组的多个元素找到最大的 3 的倍数。
示例
输入
nums = {9, 6, 2, 3, 8, 2, 1}
输出
9 8 6 3 2 2
解释 - 在这里，我们使用了除“1”之外的所有数组元素来创建最大的 3 的倍数。
输入
nums = {9, 6, 9, 3, 3, 9}
输出
9 9 9 6 3 3
解释 - 在这里，我们使用了所有数组元素，因为它们都能被 3 整除。
输入
nums = {7, 6, 3, 7}
输出
6 3
解释 - 在这里，我们需要从数组中移除 7 和 7 以获得最大的 3 的倍数。
方法 1
在这种方法中，我们将使用位操作技术来获取数组元素的所有可能组合。我们将检查每个组合是否为 3 的倍数。如果是，我们将将其与之前的最大组合进行比较，如果当前组合更大，则更新它。
算法
步骤 1 - 使用 sort() 方法按降序对数组进行排序。
步骤 2 - 定义 'largestNum' 向量来存储最大的可能组合。
步骤 3 - 使用循环从 1 到 2N 遍历，因为我们对每个数组元素有 2 个选择。我们可以选择当前元素或将其留下。因此，我们共有 2N 个组合。
步骤 4 - 在循环中，定义 'temp' 向量来存储当前组合。此外，遍历数组元素。如果 m 中的第 p 位为“1”，则将 nums[p] 插入到“temp”列表中。
步骤 5 - 接下来，执行 checkForMul3() 函数以检查当前组合是否为 3 的倍数。
步骤 5.1 - 在 checkForMul3() 函数中，对所有元素求和，如果和能被 3 整除则返回 true。否则，返回 false。
步骤 6 - 如果 checkForMul3() 函数返回 true，请按照以下步骤操作。
步骤 6.1 - 如果 temp 的大小大于 largestNum，则使用 temp 更新 largestNum。
步骤 6.2 - 如果 temp 的大小等于 largestNum，则遍历两个列表并比较两个列表的每个元素。
步骤 6.3 - 如果任何索引 temp[p] 大于 largestNum[q]，则使用 temp 更新 largestNum 并中断循环。同样，如果任何索引 temp[p] 小于 largestNum[q]，则中断循环。
步骤 7 - 返回“largestNum”列表。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool checkForMulOf3(const vector<int> &temp) {
int s = 0;
for (int num : temp) {
s += num;
}
// Return true if the sum is divisible by 3
return (s % 3 == 0);
}
vector<int> GetLargestMul3(vector<int> &nums) {
// Sort in reverse order
sort(nums.begin(), nums.end(), greater<int>());
vector<int> largestNum;
// Using bit manipulation technique
for (int m = 1; m < (1 << nums.size()); m++) {
vector<int> temp;
// Take array elements according to the set-bits position
for (int p = 0; p < nums.size(); p++) {
if (m & (1 << p)) {
temp.push_back(nums[p]);
}
}
// When a new subset is multiple of 3
if (checkForMulOf3(temp)) {
// When the size of temp is greater than largestNum
if (temp.size() > largestNum.size()) {
largestNum = temp;
} else if (temp.size() == largestNum.size()) {
for (int p = 0; p < temp.size(); p++) {
if (temp[p] > largestNum[p]) {
largestNum = temp;
break;
} else if (temp[p] <largestNum[p]) {
break;
}
}
}
}
}
return largestNum;
}
int main() {
vector<int> nums = {9, 6, 2, 3, 8, 2, 1};
vector<int> largestMultiple = GetLargestMul3(nums);
if (largestMultiple.size() > 0) {
cout << "The largest multiple of 3: ";
for (int num : largestMultiple) {
cout << num << " ";
}
} else {
cout << "It is not possible to find multiple of 3.";
}
cout << endl;
return 0;
}
输出
The largest multiple of 3: 9 8 6 3 2 2
时间复杂度 - O(N*2N)，以获得所有可能的数组组合并对其元素求和。
空间复杂度 - O(N) 用于将数组元素存储到“temp”列表中。
方法 2
在这种方法中，我们将使用三个队列根据其除以 3 后的余数来存储数组元素。之后，我们将根据数组元素的总和从特定队列中移除数组元素。
算法
步骤 1 - 使用 sort() 方法对数组进行排序。
步骤 2 - 定义三个名为“que0”、“que1”和“que2”的队列。
步骤 3 - 遍历数组并将元素插入队列。如果 nums[p] % 3 为 0，则将其插入 que0。如果 nums[p] % 3 为 1，则将数组元素插入 que1。否则，将数组元素插入 que2。另外，将元素的总和存储在 nums_sum 变量中。
步骤 4 - 如果 num_sum % 3 为 1，则从 que1 中移除 1 个元素。如果 que1 为空，则如果 que2 的大小大于或等于 2，则从 que2 中移除 2 个元素。否则，返回 0。
步骤 5 - 如果 num_sum % 3 为 2，则如果 que2 不为空，则从 que2 中移除 2 个元素。否则，如果 que1 包含超过 2 个元素，则从 que1 中移除 2 个元素。否则，返回 0。
步骤 6 - 创建一个 temp[] 数组并将所有队列的元素插入到 temp 数组中。之后，按降序对 temp 数组进行排序。
步骤 7 - 打印数组元素。
示例
#include <bits/stdc++.h>
using namespace std;
int GetLargestMul3(int nums[], int size) {
// Sort array in increasing order
sort(nums, nums + size);
// Definining 3 queues
queue<int> que0, que1, que2;
// Insert elements in these queues according to reminder and sum them
int p, num_sum;
for (p = 0, num_sum = 0; p < size; ++p) {
// Sum numbers
num_sum += nums[p];
// Insert in queues
if ((nums[p] % 3) == 0)
que0.push(nums[p]);
else if ((nums[p] % 3) == 1) {
que1.push(nums[p]);
} else {
que2.push(nums[p]);
}
}
// When sum%3 == 1
if ((num_sum % 3) == 1) {
// Pop out one item from que1
if (!que1.empty()) {
que1.pop();
}
// Pop out two items from que2
else {
if (que2.size() >= 2) {
que2.pop();
que2.pop();
} else {
return 0;
}
}
}
// When sum%3 == 2
else if ((num_sum % 3) == 2) {
// Pop out one item from que2
if (!que2.empty())
que2.pop();
// Pop out two items from que1
else {
if (que1.size() >= 2) {
que1.pop();
que1.pop();
} else {
return 0;
}
}
}
int temp[size], top = 0;
// Insert elements of the first queue in the array
while (!que0.empty()) {
temp[top++] = que0.front();
que0.pop();
}
// Insert elements of the second queue in the array
while (!que1.empty()) {
temp[top++] = que1.front();
que1.pop();
}
// Insert elements of the third queue in the array
while (!que2.empty()) {
temp[top++] = que2.front();
que2.pop();
}
// Sort the array in reverse order
sort(temp, temp + top, greater<int>());
cout << "The largest divisible of 3 we can create is - ";
// Show number
for (int p = 0; p < top; ++p)
cout << temp[p] << " ";
return top;
}
int main() {
int nums[] = {9, 6, 2, 3, 8, 2, 1};
int size = sizeof(nums) / sizeof(nums[0]);
if (GetLargestMul3(nums, size) == 0)
cout << "It is not possible to find the largest multiple of 3.";
return 0;
}
输出
The largest divisible of 3 we can create is - 9 8 6 3 2 2
时间复杂度 - O(N)
空间复杂度 - O(N) 用于将元素存储在队列中。
浏览量：100
