题面描述:

数据重删是一种用于节约存储空间的技术，旨在识别和处理存储池内的重复数据块。其基本思路是，在多个重复的数据块中仅保留一份，通过地址指针指向这份唯一的数据。给定一组数据及其块的大小，需要设计一个方法判断当前数据块是否与之前的数据库重复。如果发现重复，需将该数据库删除，并在首次出现的数据库后增加重复计数，最终输出处理后的数据内容，格式为以空格分隔的数字，且最后没有空格。输入包括一个整数 $N$（数据个数）、一个整数 $K$（数据块大小）及 $N$ 个整数（数据值），输出则为去除重复数据后的结果，例如对于输入 8 2 1 2 3 4 1 2 3 4，输出为 1 2 2 3 4 2。

题目思路

该题的要点是要统计出要多少个数据块，所以先将数组按照大小为k进行分段，并且对每一段进行计数，将相同的数据块一次输出。可以考虑使用map来对数据块计数。计数完毕后，再重新分段遍历数组，当map中存在该数据段时，一次性将其输出，并且将该数据段从map中删除，防止重复输出。

解题步骤

1. 数据输入与初始化：

   • 读取输入数据的个数 $N$ 和数据块的大小 $K$。
   • 将输入的 $N$ 个整数存储在一个数组中。

2. 数据分块：

   • 使用一个循环将数据按大小为 $K$ 进行分割，生成一个字符串形式的子数组。
   • 使用 stringstream 将每个子数组的元素连接为字符串，并存入一个 vector<string> 中。

3. 统计出现频次：

   • 使用 unordered_map 来记录每个子数组字符串的出现次数。
   • 另一个 unordered_map 用于存储子数组首次出现的索引，以便后续排序。

4. 构建结果集合：

   • 遍历统计结果，将子数组、频次和索引封装成三元组，并存储在一个向量中。
   • 根据首次出现的索引对三元组向量进行排序，确保输出顺序与输入一致。

5. 格式化输出：

   • 将处理后的结果拼接为最终输出字符串，确保格式正确，且没有多余的空格。

代码

python

n = int(input())  # 读取数组 a 的长度
k = int(input())  # 读取分割 a 的块大小
a = list(map(int, input().split()))  # 读取数组 a

parts = []  # 存储分割后的子数组
# 将数组 a 分成 k 份
left = 0
while left < n:
    right = min(left + k - 1, n - 1)  # 确定当前子数组的右边界
    parts.append(" ".join(map(str, a[left:right + 1])))  # 将当前子数组转为字符串并添加到 parts 列表中
    left = right + 1  # 更新左边界，准备处理下一个子数组

mp = {}  # 用于存储子数组出现的频次
idx = {}  # 用于存储子数组第一次出现的索引
for i in range(len(parts)):
    if parts[i] not in mp:  # 如果子数组第一次出现
        mp[parts[i]] = 1  # 将其频次设为 1
        idx[parts[i]] = i  # 记录其首次出现的索引
    else:
        mp[parts[i]] += 1  # 否则增加其频次

res = []  # 用于存储 (子数组, 频次, 索引) 的三元组
for key in mp:
    res.append((key, mp[key], idx[key]))  # 构建三元组并添加到 res 列表中
res.sort(key=lambda x: (x[2]))  # 根据索引对 res 列表进行排序

output = ""  # 初始化输出字符串
for x in res:
    output += x[0] + " " + str(x[1]) + " "  # 将每个三元组的内容拼接到输出字符串中
output = output[:-1]  # 去掉最后多余的空格

print(output)  # 输出结果

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        List<String> parts = new ArrayList<>();
        int left = 0;
        // 把数组切成长k份
        while (left < n) {
            int right = Math.min(left + k - 1, n - 1);
            StringBuilder sb = new StringBuilder();
            for (int i = left; i <= right; i++) {
                if (i > left) {
                    sb.append(" ");
                }
                sb.append(sc.nextInt());
            }
            parts.add(sb.toString());
            left = right + 1;
        } 
        // 计算每个部分的出现次数 以及 第一次出现的位置
        Map<String, Integer> mp = new HashMap<>();
        Map<String, Integer> idx = new HashMap<>();
        for (int i = 0; i < parts.size(); i++) {
            String part = parts.get(i);
            if (!mp.containsKey(part)) {
                mp.put(part, 1);
                idx.put(part, i);
            } else {
                mp.put(part, mp.get(part) + 1);
            }
        }
        // 按照第一次出现的位置排序
        List<List<Object>> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : mp.entrySet()) {
            List<Object> tuple = new ArrayList<>();
            tuple.add(entry.getKey());
            tuple.add(entry.getValue());
            tuple.add(idx.get(entry.getKey()));
            res.add(tuple);
        }
        res.sort(Comparator.comparingInt(list -> (int) list.get(2)));
        // 输出结果
        StringBuilder output = new StringBuilder();
        for (List<Object> tuple : res) {
            output.append(tuple.get(0)).append(" ").append(tuple.get(1)).append(" ");
        }
        System.out.println(output.toString().trim());
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>

using namespace std;

// 将字符串按给定的分隔符分割成字符串向量
vector<string> split(const string& str, char delimiter) {
    vector<string> result;
    stringstream ss(str);
    string token;
    while (getline(ss, token, delimiter)) {
        result.push_back(token);
    }
    return result;
}

int main() {
    int n, k;
    cin >> n >> k;  // 读取数组 a 的长度 n 和分割大小 k
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];  // 读取数组 a 的元素
    }
    
    vector<string> parts;  // 存储分割后的子数组
    int left = 0;
    while (left < n) {
        int right = min(left + k - 1, n - 1);  // 确定当前子数组的右边界
        stringstream ss;
        for (int i = left; i <= right; i++) {
            if (i > left) {
                ss << " ";  // 在子数组元素之间添加空格
            }
            ss << a[i];  // 将当前元素添加到子数组字符串中
        }
        parts.push_back(ss.str());  // 将当前子数组字符串添加到 parts 向量中
        left = right + 1;  // 更新左边界，准备处理下一个子数组
    }
    
    unordered_map<string, int> mp;  // 用于存储子数组出现的频次
    unordered_map<string, int> idx;  // 用于存储子数组第一次出现的索引
    for (int i = 0; i < parts.size(); i++) {
        if (mp.count(parts[i]) == 0) {  // 如果子数组第一次出现
            mp[parts[i]] = 1;  // 将其频次设为 1
            idx[parts[i]] = i;  // 记录其首次出现的索引
        } else {
            mp[parts[i]]++;  // 否则增加其频次
        }
    }
    
    // 构建 (子数组, 频次, 索引) 的三元组向量
    vector<tuple<string, int, int>> res;
    for (const auto& [key, value] : mp) {
        res.emplace_back(key, value, idx[key]);
    }
    
    // 根据索引对三元组向量进行排序
    sort(res.begin(), res.end(), [](const auto& a, const auto& b) {
        return get<2>(a) < get<2>(b);
    });
    
    string output;  // 初始化输出字符串
    for (const auto& t : res) {
        string part = get<0>(t);
        int count = get<1>(t);
        int _ = get<2>(t);  // 或者忽略这个变量如果不需要
        output += part + " " + to_string(count) + " ";  // 将每个三元组的内容拼接到输出字符串中
    }
    output.pop_back();  // 去掉最后多余的空格
    
    cout << output << endl;  // 输出结果
    return 0;
}

视频讲解

数据重删是一种节约存储空间的技术，通常情况下，在数据存储池内是有很多重复的数据库。重删则是将这些重复的数据块找出并处理的技术。简单地说重删，就是将$N$份重复的数据快仅保留$1$份，并将$N-1$份数据的地址指针指向唯一的那一份。

我们输入一串存储的数据，用$N$表示数据个数，用$K$标识号数据库的大小，设计一个方法判断当前数据块是否和前面的数据库有重复，两个数据库内容完全一样则表示重复。如果重复则将这个数据库删除，并且在第一个出现数据库的后面增加重复数据的计数，输出经过重复之后的内容。

解答要求

时间限制：$C/C++ 1000ms$，其他语言 $2000ms$

内存限制：$C/C++ 256MB$, 其他语言$512MB$

输入

8输入数据的个数

2数据库的大小

1 2 3 4 1 2 3 4依次是数据值

输出

1 2 2 3 4 2输出结果为去除重复数据后的结果，输出结果最后没有空格，以数字结尾，输出内容不改变输入数据库的顺序

样例1

输入

8
2 
1 2 3 4 1 2 3 4

输出

1 2 2 3 4 2 

解释

总共$8$个数据，数据库的大小为$2$，按新窗口进行切片表示一个数据块，分别得到数据库为[1,2],[3,4],[1,2],[3,4]其中第一个数据块和第三个数据块相同，第二个数据块和第四个数据块相同，可以分别进行重测，重测之后数据库$[1,2]$的计数变为$2$，表示有两个相同的数据块$[1,2]$,同理$[3,4]$d的数据块计数性变为$2$

样例2

输入

8
3
3 4 5 3 4 5 5 4 

输出

3 4 5 2 5 4 1