面试题：C++ 位运算优化数据压缩

Question

给定一个包含0到255之间整数的数组，要求使用C++ 位运算来实现一种简单的数据压缩算法。思路是将多个整数合并到更少的字节中，例如，假设每个字节有8位，你可以尝试将多个小整数的部分位组合到一个字节中。请实现压缩和解压缩函数，并分析算法的空间复杂度和时间复杂度。

Answer 1

#include <iostream>
#include <vector>

// 压缩函数
std::vector<char> compress(const std::vector<int>& data) {
    std::vector<char> compressed;
    char currentByte = 0;
    int bitIndex = 0;

    for (int num : data) {
        for (int i = 0; i < 8 && bitIndex < 8; ++i, ++bitIndex) {
            currentByte |= ((num >> i) & 1) << bitIndex;
            if (bitIndex == 7) {
                compressed.push_back(currentByte);
                currentByte = 0;
                bitIndex = 0;
            }
        }
    }
    if (bitIndex > 0) {
        compressed.push_back(currentByte);
    }
    return compressed;
}

// 解压缩函数
std::vector<int> decompress(const std::vector<char>& compressed) {
    std::vector<int> decompressed;
    int currentInt = 0;
    int bitIndex = 0;

    for (char byte : compressed) {
        for (int i = 0; i < 8 && bitIndex < 8; ++i, ++bitIndex) {
            currentInt |= ((byte >> i) & 1) << bitIndex;
            if (bitIndex == 7) {
                decompressed.push_back(currentInt);
                currentInt = 0;
                bitIndex = 0;
            }
        }
    }
    if (bitIndex > 0) {
        decompressed.push_back(currentInt);
    }
    return decompressed;
}

复杂度分析

1. 时间复杂度：
   • 压缩函数：对于compress函数，它遍历输入数组中的每个整数，每个整数最多处理8位。因此，时间复杂度为$O(n)$，其中n是输入数组data的大小。
   • 解压缩函数：对于decompress函数，它遍历压缩后的字节数组，每个字节最多处理8位。因此，时间复杂度也为$O(m)$，其中m是压缩后数组compressed的大小。在理想情况下，m小于n，但最坏情况下，m可能与n相近（例如数据本身就无法有效压缩），所以整体时间复杂度还是$O(n)$。
2. 空间复杂度：
   • 压缩函数：compress函数创建了一个新的std::vector<char>来存储压缩后的数据。在最坏情况下，压缩后的数据大小可能接近原始数据大小（例如数据无法有效压缩时），所以空间复杂度为$O(n)$。
   • 解压缩函数：decompress函数创建了一个新的std::vector<int>来存储解压缩后的数据。其空间复杂度为$O(n)$，因为解压缩后的数据大小与原始输入数据大小相同。

总体而言，压缩和解压缩函数的时间复杂度和空间复杂度均为$O(n)$。