C++ 中重新排列远程条形码

2025年5月17日 | 阅读12分钟

引言

“重排不相邻条形码” 是一个在计算机科学领域，尤其是在算法设计和优化中经常遇到的计算问题。挑战在于重新组织由整数表示的条形码序列，使得任意两个相邻的条形码都不相同。这个问题类似于寻找一种排列方式，其中每个条形码与其他相同值的条形码都有足够的“距离”，从而确保一个均衡且不重复的序列。

在 C++ 中，解决这个问题通常需要利用诸如堆（优先队列）和哈希表等数据结构。堆有助于高效地检索最常出现的条形码，这些条形码需要间隔开以避免连续重复。通过使用哈希表，可以跟踪条形码的频率。解决方案涉及反复将最常出现的条形码放置在下一个可用位置，然后暂时将其搁置，以便放置另一个不同的条形码。这种方法确保排列符合不相邻相同条形码的约束。

在 C++ 中实现此解决方案提供了应用贪心算法和优先队列的实际示例，展示了该语言在处理复杂数据操作和优化问题方面的优势。

方法 1：基本方法

程序

 
 #include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    // Frequency map to count occurrences of each barcode
    unordered_map<int, int> freqMap;
    for (int code : barcodes) {
        freqMap[code]++;
    }
    // Priority queue to sort barcodes by frequency
    priority_queue<pair<int, int>> maxHeap;
    for (auto& entry : freqMap) {
        maxHeap.push({entry.second, entry.first});
    }
    vector<int> result;
    pair<int, int> prev = {0, 0}; // Previous barcode and its frequency
    while (!maxHeap.empty()) {
        auto current = maxHeap.top();
        maxHeap.pop();    
        // Add the most frequent barcode to the result
        result.push_back(current.second);
        // Decrease the frequency
        current.first--;
        // Push the previous element back into the heap if it has the remaining frequency
        if (prev.first > 0) {
            maxHeap.push(prev);
        }
        // Update the previous element to the current element
        prev = current;
    }
    return result;
}
int main() {
    vector<int> barcodes = {1, 1, 1, 2, 2, 3};
    vector<int> result = rearrangeBarcodes(barcodes);
    for (int code : result) {
        cout << code << " ";
    }
    cout << endl;
    return 0;
}  

输出

 
1 2 1 3 2 1

说明

频率计数
第一步是计算输入列表中的每个条形码出现的次数。这可以使用哈希表（或 C++ 中的无序映射）完成，其中键是条形码，值是其出现次数的计数。此步骤有助于识别最常出现的条形码，这些条形码需要仔细放置以避免相邻重复。
优先队列（最大堆）
下一步是使用优先队列（实现为最大堆）来根据其频率跟踪条形码。在此优先队列中，频率最高的条形码始终位于顶部。这允许高效地检索下一个应放置的条形码，以最大化相同条形码之间的距离。
放置逻辑
核心逻辑涉及在结果列表的下一个可用位置反复放置最常出现的条形码。放置条形码后，将其频率减一。为确保同一条形码不连续放置，算法会暂时搁置先前放置的条形码，直到放置了另一个条形码后才将其重新插入优先队列。
维护先前条形码
使用代表先前放置的条形码及其剩余计数对，以确保它不会连续放置。在放置新条形码后，如果仍需要，则将先前条形码及其更新的计数推回优先队列。
构建结果
此过程一直持续到所有条形码都被放入结果列表中。通过始终选择最常出现的条形码并仔细管理先前放置的条形码，算法可确保没有两个相邻的位置包含相同的条形码。

输出

最后，返回并打印重排后的列表，展示所需的非重复序列。

复杂度分析

时间复杂度

时间复杂度为 O(nlogk)，其中 n 是条形码的数量，k 是唯一条形码的数量。

构建频率映射需要 O(n) 时间。

构建优先队列需要 O(klogk) 时间。

每次从优先队列插入和提取操作需要 O(logk)，由于有 n 次此类操作，因此这部分总共需要 O(log) 时间。

空间复杂度

空间复杂度为 O(n+k)。

频率映射需要 O(k) 空间来存储每个唯一条形码的计数。

优先队列需要 O(k) 空间来根据频率存储条形码。

结果向量需要 O(n) 空间来存储重排后的条形码。

方法 2：使用贪心算法和排序

在贪心算法和排序方法中，目标是通过优先放置最常出现的条形码来重排不相邻条形码。此方法涉及根据条形码的频率以降序排序。通过贪婪地选择和交替使用最常出现的条形码，算法可确保没有两个相邻的位置包含相同的条形码。这种方法有效地利用排序来创建条形码的平衡分布，优化了实际实现的空间和时间复杂度。

程序

 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    // Frequency map to count occurrences of each barcode
    unordered_map<int, int> freqMap;
    for (int code : barcodes) {
        freqMap[code]++;
    }
    // Create a vector of pairs (frequency, barcode) and sort it
    vector<pair<int, int>> freqVector;
    for (auto& entry : freqMap) {
        freqVector.push_back({entry.second, entry.first});
    }
    sort(freqVector.rbegin(), freqVector.rend());
    // Place barcodes in the result vector
    vector<int> result(barcodes.size());
    int index = 0;
    for (auto& entry : freqVector) {
        int freq = entry.first;
        int code = entry.second;
        for (int i = 0; i < freq; ++i) {
            result[index] = code;
            index += 2;
            if (index >= barcodes.size()) {
                index = 1; // Switch to odd indices after filling even indices
            }
        }
    }
    return result;
}
int main() {
    vector<int> barcodes = {1, 1, 1, 2, 2, 3};
    vector<int> result = rearrangeBarcodes(barcodes);
    for (int code : result) {
        cout << code  << " ";
    }
    cout << endl;
    return 0;
}   

输出

 
1 2 1 2 1 3

说明

频率计数
最初，算法使用哈希表计算每个条形码的频率。此步骤提供了对哪些条形码出现频率最高的见解，这对于后续的放置决策至关重要。
按频率排序
接下来，算法根据条形码的频率以降序对其进行排序。通过这样做，最常出现的条形码会排在前面，确保在放置期间首先考虑它们。
交替放置
此方法的一个关键方面在于放置策略。从索引 0 开始，算法开始将最常出现的条形码放置在偶数索引（0、2、4 等）上。在用完偶数索引后，它会切换到奇数索引（1、3、5 等）。这种交替模式保证了没有两个相同的条形码相邻。
完成序列
算法继续此过程，直到所有条形码都放置在重排后的序列中。通过优先放置最常出现的条形码并交替其位置，算法可在遵循避免连续重复的约束的同时实现均衡分布。
优化
按频率对条形码进行排序可优化放置过程，确保最常出现的条形码首先放置，从而最大程度地降低相邻重复的可能性。这种贪心策略通过关注基于局部最优解决方案的即时决策来简化问题。

复杂度分析

时间复杂度

频率计数：此步骤涉及一次遍历输入条形码列表，时间复杂度为 O(n)，其中 n 是条形码的数量。

按频率排序：按频率对条形码进行排序需要 O(klogk) 时间，其中 k 是唯一条形码的数量。

放置：将条形码放置在交替位置需要 O(n) 时间，因为每个条形码都放置一次。

总体而言，时间复杂度由排序步骤决定，结果为 O(nlogk)，其中 n 是条形码的数量，k 是唯一条形码的数量。

空间复杂度

频率映射：频率映射所需的空间为 O(k)，其中 k 是唯一条形码的数量。

已排序条形码：存储排序后的条形码可能需要额外的 O(n) 空间。

结果向量：结果向量所需的空间为 O(n)。

因此，总体空间复杂度为 O(n+k)，其中 n 是条形码的数量，k 是唯一条形码的数量。

方法 3：使用双指针技术

方法 3 采用双指针技术来解决重排不相邻条形码问题。此方法涉及使用优先队列来根据频率管理条形码的放置。通过使用两个指针在放置期间在偶数和奇数索引之间交替，算法可确保没有两个相同的条形码相邻。此方法通过贪婪地优先放置最常出现的条形码，同时遵循保持重复项之间足够距离的约束来有效地处理问题。它优化了时间和空间复杂度，使其成为重排条形码的实用解决方案。

程序

 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    unordered_map<int, int> freqMap;
    for (int code : barcodes) {
        freqMap[code]++;
    }
    priority_queue<pair<int, int>> maxHeap;
    for (auto& entry : freqMap) {
        maxHeap.push({entry.second, entry.first});
    }
    vector<int> result(barcodes.size());
    int index = 0;
    while (!maxHeap.empty()) {
        auto current = maxHeap.top();
        maxHeap.pop();
        for (int i = 0; i < current.first; ++i) {
            result[index] = current.second;
            index += 2;
            if (index >= barcodes.size()) {
                index = 1;
            }
        }
    }
    return result;
}
int main() {
    vector<int> barcodes = {1, 1, 1, 2, 2, 3};
    vector<int> result = rearrangeBarcodes(barcodes);
    for (int code : result) {
        cout << code << " ";
    }
    cout << endl;
    return 0;
}   

输出

 
1 2 1 2 1 3

说明

频率计数
最初，算法使用哈希表计算每个条形码的频率，存储每个条形码的计数。
优先队列构造
接下来，算法构建一个优先队列（实现为最大堆）来管理条形码的放置。优先队列根据频率对条形码进行排序，确保最常出现的条形码首先被考虑。
双指针放置
此方法的核心涉及使用两个指针在偶数和奇数索引处交替填充结果向量。从最常出现的条形码开始，算法将其放置在偶数索引处，然后继续将下一个最常出现的条形码放置在奇数索引处。通过这样做，算法可确保没有两个相同的条形码相邻。

完成序列

此放置策略一直持续到所有条形码都放置在重排后的序列中。优先队列有效地处理最常出现条形码的选择，而双指针技术可确保均衡分布。

优化
利用优先队列可优化放置过程，始终选择最常出现的条形码进行放置。双指针技术通过关注基于局部最优解决方案的即时决策来简化问题，从而提供实用且高效的解决方案。

复杂度分析

时间复杂度

频率计数：计算每个条形码的频率需要一次遍历输入列表，时间复杂度为 O(n)，其中 n 是条形码的数量。

优先队列构造：构建优先队列需要 O(klogk) 时间，其中 k 是唯一条形码的数量。

放置：将条形码放置在交替位置需要 O(n) 时间，因为每个条形码都放置一次。

总体而言，时间复杂度由优先队列构造步骤决定，结果为 O(nlogk)，其中 n 是条形码的数量，k 是唯一条形码的数量。

空间复杂度

频率映射：频率映射所需的空间为 O(k)，其中 k 是唯一条形码的数量。

优先队列：优先队列的空间复杂度为 O(k)，用于根据频率存储条形码。

结果向量：结果向量所需的空间为 O(n)。

方法 4：使用桶排序和重排

方法 4 采用桶排序和重排策略来解决重排不相邻条形码问题。此方法涉及首先计算每个条形码的频率，然后根据其频率将它们排序到桶中。通过首先重新分发最高频率桶中的条形码并填充结果数组中的空隙，算法可确保均衡分布，同时避免连续重复。此方法通过有效地排序和重排条形码来优化时间和空间复杂度，使其成为解决此问题的实用解决方案。

程序

 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    unordered_map<int, int> freqMap;
    for (int code : barcodes) {
        freqMap[code]++;
    }
    vector<int> buckets[barcodes.size() + 1];
    for (auto& entry : freqMap) {
        buckets[entry.second].push_back(entry.first);
    }
    vector<int> result;
    for (int i = barcodes.size(); i > 0; --i) {
        for (int code : buckets[i]) {
            for (int j = 0; j < i; ++j) {
                result.push_back(code);
            }
        }
    }
    vector<int> finalResult(barcodes.size());
    int index = 0;
    for (int i = 0; i < result.size(); ++i) {
        finalResult[index] = result[i];
        index += 2;
        if (index >= barcodes.size()) {
            index = 1;
        }
    }
    return final result;
}
int main() {
    vector<int> barcodes = {1, 1, 1, 2, 2, 3};
    vector<int> result = rearrangeBarcodes(barcodes);
    for (int code : result) {
        cout << code << " ";
    }
    cout << endl;
    return 0;
}   

输出

 
1 2 1 2 1 3

说明

频率计数
最初，算法计算输入列表中每个条形码出现的次数。此步骤可深入了解条形码的频率分布。
桶排序
条形码根据其频率排序到桶中。每个桶代表一个特定的频率计数，可实现条形码的高效组织。
重排
算法通过从最高频率桶开始进行重排。来自该桶的条形码放置在结果数组中，确保没有两个相同的条形码相邻。过程继续使用较低频率的桶，直到所有条形码都放置为止。
完成序列
重排后，算法可能会在结果数组中留下一些空隙。这些空隙用来自剩余桶的条形码填充，确保完整且均衡的重排。
优化
利用桶排序可优化放置过程，通过将具有相似频率的条形码分组。此方法通过将问题分解为更小、更易于管理的任务来简化问题，从而实现更高效的解决方案。

复杂度分析

时间复杂度

频率计数：计算每个条形码的频率需要一次遍历输入列表，时间复杂度为 O(n)，其中 n 是条形码的数量。

桶排序：将条形码根据其频率分桶排序需要 O(k) 时间，其中 k 是唯一条形码的数量。

重排：重排条形码涉及遍历桶并将它们放置在结果数组中，这也需要 O(k) 时间。

总体而言，时间复杂度为 O(n+k)，其中 n 是条形码的数量，k 是唯一条形码的数量。

空间复杂度

频率映射：频率映射所需的空间为 O(k)，其中 k 是唯一条形码的数量。

桶：存储桶可能需要额外的 O(n) 空间，每个桶包含条形码的一个子集。

结果向量：结果向量所需的空间为 O(n)。

因此，总体空间复杂度为 O(n+k)，其中 n 是条形码的数量，k 是唯一条形码的数量。

性质

频率约束
条形码可能在输入序列中重复，具有不同的频率。
重排后的序列必须确保没有两个相邻的条形码相同，在相同条形码之间保持最小距离。
最佳排列
最佳排列可最大化相同条形码之间的距离，从而促进整个序列的均衡分布。
实现这种平衡可提高可读性，并减少条形码系统中误解的可能性。
高效算法
存在各种高效算法来解决该问题，每种算法都有其在时间和空间复杂度之间的权衡。
贪心算法、排序技术（例如桶排序）和基于优先队列的方法是高效解决方案的常见选择。
算法的选择取决于输入大小、频率分布和期望的性能指标等因素。
时空权衡
不同的算法在时间和空间复杂度之间提供权衡。例如；一些方法可能会优先考虑最小化空间使用，但会增加计算时间。
理解这些权衡允许开发人员根据应用程序的特定要求选择最合适的算法。
实现灵活性
可以使用各种编程范式来处理该问题，包括迭代和递归方法。
实现灵活性允许开发人员根据算法的复杂性、编程语言功能和性能考虑来定制解决方案。
处理边界情况
对于边缘情况需要特别注意，例如唯一条形码数量少于序列中总位置数的情况。
设计鲁棒的解决方案来处理边缘情况可确保算法在各种输入场景下的正确性和可靠性。
可扩展性
所选算法的效率对于可扩展性至关重要，尤其是在处理大型输入大小时。
可扩展性考虑因素包括算法的计算复杂性及其对解决方案性能的影响（随着输入大小的增加）。

下一个主题Mersenne-primes-in-cpp

← 上一个下一个 →

C++ 中重新排列远程条形码

引言

方法 1：基本方法

程序

说明

复杂度分析

方法 2：使用贪心算法和排序

程序

说明

复杂度分析

方法 3：使用双指针技术

程序

说明

复杂度分析

方法 4：使用桶排序和重排

程序

说明

复杂度分析

性质

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中重新排列远程条形码

引言

方法 1：基本方法

程序

说明

复杂度分析

方法 2：使用贪心算法和排序

程序

说明

复杂度分析

方法 3：使用双指针技术

程序

说明

复杂度分析

方法 4：使用桶排序和重排

程序

说明

复杂度分析

性质

相关帖子

C++ 中检查主教是否可以吃掉兵

C++ 中关于斐波那契数列的有趣事实