C++ 找到最大的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)，用于将元素存储在队列中。