資料結構
網路
關係資料庫管理系統 (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
