实验时间：10.14

目录

Puzzle 1：Frequency Moments

 Puzzle 2：a maximal array is sorted or not

二分查找(仅对有序数组查找有效)

源代码：（只需要修改这几个参数即可）

---

Puzzle 1：Frequency Moments

频繁元素

从数据流中获取出现次数最多的三个元素

要求：空间复杂度为O(k)

简述算法过程：

continue代表执行下一次循环

将若干数据，按顺序放入长度为K的数组，直至全部填满，统计K个不同数据的次数；

然后依次遍历剩下的所有数据，对每个数据执行如下操作；

判断数据在数组中查找是否存在；

存在，则该元素次数加1，continue；

不存在，看数组是否有空位置，能否将数据放入数组；

有空位置，则放入数组中，则该元素次数置为1，continue；

没有空位置，则其他所有次数减1，continue；

最后，统计完后，将数组元素按照次数排序；

输出数组中次数不为0的元素。

实验代码：

void Solution1(Env& env) {//num 数组 为数值，初始化为 0//t 数组 为出现的次数，初始化为 0int* num = new int[K] {};int* t = new int[K] {};// isHave 表示，元素在数组的下标，-1不存在// ownSpace 表示，数组是否有空位放入 1有 0没有int isHave = -1, ownSpace = 0;//遍历所有元素for (size_t i = 0, temp = env.get_data(), differentNum = 0; temp != -1; ++i) {//默认元素不在数组，数组没有空间存放isHave = -1;ownSpace = 0;//判断元素是否存在，存在返回下标，并且次数++，不存在返回 -1isHave = IsExist(t, num, temp);// 初始化 数组元素，放入K个不同的元素，相同的元素 累加次数if (differentNum < K) {//判断 当前元素 是否存在，-1 代表不存在if (isHave == -1) {num[differentNum] = temp;++t[differentNum];++differentNum;}} else {//初始化 数组后， 数组已经满了，处理剩下的元素//isHave -1 数据不在数组中if (isHave == -1) {//数组 是否 有空位 放入元素for (size_t j = 0; j != K; ++j) {//找到空位，可以放入数据if (!t[j]) {num[j] = temp;++t[j];ownSpace = 1;break;}}//没有空位，所有元素次数--if (!ownSpace) {for (size_t j = 0; j != K && t[j]; ++j) {--t[j];}}}}temp = env.get_data();}//快速排序，输出QuickSort(t, num, 0, K - 1);OutPut(num, t);
}

实验结果（含时间、空间、输出结果）：

 Puzzle 2：a maximal array is sorted or not

有序数组

判断一个极大的数组是否是有序数组

要求：时间复杂度为O(log n)

简述算法过程：

随机找一个位置，从数组中取出对应的数值，在数组中进行二分查找。

二分查找，找到了，则认为极大的数组是近似有序数组；

二分查找，没找到，则认为极大的数组不是近似有序数组。

二分查找(仅对有序数组查找有效)

假设数组递增，每次将要查找的值res与数组下标为mid元素比较，mid=(left+right)/2；

小于mid，right = mid – 1，

大于mid，left = mid + 1，

等于则找到了，break，

直到left==right时，还未找到，则未找到该元素

实验代码：

void Solution2(Env& env) {srand(time(NULL));//随机选择一个位置，作为要查询的数据int posi = rand() % NumSize, res = env.data[posi];//初始化数据，int left = 0, right = NumSize - 1, mid = 0;//flag标志 数组递减 1 递增 0, 有序为 2int flag = env.data[left] >= env.data[right] ? 1 : 0;//二叉搜索while (left <= right) {//mid 为 均值//>>优先级 比 left低//left + right可能越界，因此，left + ((right - left)更稳妥些mid = left + ((right - left) >> 1);//根据比较，缩小范围if (env.data[mid] < res) {if (flag) {right = mid - 1;} else {left = mid + 1;}} else if (env.data[mid] > res) {if (flag) {left = mid + 1;} else {right = mid - 1;}} else {if (flag) {cout << "极大的数组是近似 递减 有序数组！" << endl;} else {cout << "极大的数组是近似 递增 有序数组！" << endl;}flag = 2;break;}}if (flag != 2)cout << "极大的数组为 无序 数组！" << endl;
}

实验结果（含时间、空间、输出结果）：

源代码：（只需要修改这几个参数即可）

实验数据链接：

#include <iostream>
#include <fstream>
#include <ctime>
#include <string>
#include<iomanip>
#include<algorithm>
using namespace std;//FileNum为访问的文件数量，NumSize 为文件数据大小，K为均匀随机采样的数据数量，Puzzle为题目问题
const int FileNum = 5, NumSize = 40000, K = 10, Puzzle = 2;class Env {
public:int data[NumSize];int pointer_max = 0;int pointer = 0;string s = "0";Env(string str) {s = str;// test_0.csv test_1.csv test_2.csv   为第一题的测试用例// test_3.csv test_4.csv test_5.csv   为第二题的测试用例cout << "文件 " << s << endl;ifstream file("test_data/test_" + s + ".csv", ios::in);if (!file.is_open())cout << " 文件打开失败！" << endl;string temp;while (getline(file, temp)) {data[pointer_max] = stoi(temp);pointer_max++;}file.close();}int get_data() {if (!done())return data[pointer++];elsereturn -1;}bool done() {if (pointer < pointer_max)return false;elsereturn true;}
};//输出数组中的元素
void OutPut(int* num, int* t) {cout << "元素出现的次数如下：" << endl;for (size_t i = 0, count = 0; i != K; ++i) {//控制输出数据的格式,if (t[i]) {cout << setw(4) << ++count << " : " << '\t' << setw(6) << num[i] << '\t' << "次数：" << setw(6) << t[i] << '\t';if (count % 3 == 0) {cout << endl;}}}cout << endl;
}//判断元素 是否 在数组中 存在，存在 返回下标，不存在 返回 -1
int IsExist(int* t, int* num, const size_t& temp) {for (size_t j = 0; j != K && t[j]; ++j) {//是否存在，存在 次数 + 1 并且返回 下标if (num[j] == temp) {++t[j];return j;}}return -1;
}//快速排序
void QuickSort(int* t, int* num, int left, int right) {//递归left >= right时递归结束if (left >= right) {return;}//记录 开始 结尾 的下表int low = left, high = right;//下标为low，作为划分的标准int keyNum = num[left], keyT = t[left];//一直进行划分，直到high == lowwhile (left < right) {//一直找一个小于 key 的while (left < right && t[right] >= keyT) {right--;}//赋值给 lownum[left] = num[right];t[left] = t[right];//一直找一个大于 key 的while (left < right && t[left] <= keyT) {left++;}//赋值给 highnum[right] = num[left];t[right] = t[left];法2 swap 交换 //swap(num[high], num[low]);//swap(t[high], t[low]);}//将 划分值 赋给 划分停止的地方num[left] = keyNum;t[left] = keyT;法2 swap 交换 //swap(t[left], t[low]);//swap(num[left], num[low]);//递归有序QuickSort(t, num, low, left - 1);QuickSort(t, num, left + 1, high);
}void Solution1(Env& env) {//num 数组 为数值，初始化为 0//t 数组 为出现的次数，初始化为 0int* num = new int[K] {};int* t = new int[K] {};// isHave 表示，元素在数组的下标，-1不存在// ownSpace 表示，数组是否有空位放入 1有 0没有int isHave = -1, ownSpace = 0;//遍历所有元素for (size_t i = 0, temp = env.get_data(), differentNum = 0; temp != -1; ++i) {//默认元素不在数组，数组没有空间存放isHave = -1;ownSpace = 0;//判断元素是否存在，存在返回下标，并且次数++，不存在返回 -1isHave = IsExist(t, num, temp);// 初始化 数组元素，放入K个不同的元素，相同的元素 累加次数if (differentNum < K) {//判断 当前元素 是否存在，-1 代表不存在if (isHave == -1) {num[differentNum] = temp;++t[differentNum];++differentNum;}} else {//初始化 数组后， 数组已经满了，处理剩下的元素//isHave -1 数据不在数组中if (isHave == -1) {//数组 是否 有空位 放入元素for (size_t j = 0; j != K; ++j) {//找到空位，可以放入数据if (!t[j]) {num[j] = temp;++t[j];ownSpace = 1;break;}}//没有空位，所有元素次数--if (!ownSpace) {for (size_t j = 0; j != K && t[j]; ++j) {--t[j];}}}}temp = env.get_data();}//快速排序，输出QuickSort(t, num, 0, K - 1);OutPut(num, t);
}void Solution2(Env& env) {srand(time(NULL));//随机选择一个位置，作为要查询的数据int posi = rand() % NumSize, res = env.data[posi];//初始化数据，int left = 0, right = NumSize - 1, mid = 0;//flag标志 数组递减 1 递增 0, 有序为 2int flag = env.data[left] >= env.data[right] ? 1 : 0;//二叉搜索while (left <= right) {//mid 为 均值//>>优先级 比 left低//left + right可能越界，因此，left + ((right - left)更稳妥些mid = left + ((right - left) >> 1);//根据比较，缩小范围if (env.data[mid] < res) {if (flag) {right = mid - 1;} else {left = mid + 1;}} else if (env.data[mid] > res) {if (flag) {left = mid + 1;} else {right = mid - 1;}} else {if (flag) {cout << "极大的数组是近似 递减 有序数组！" << endl;} else {cout << "极大的数组是近似 递增 有序数组！" << endl;}flag = 2;break;}}if (flag != 2)cout << "极大的数组为 无序 数组！" << endl;
}// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo {
public:Algo() {cout << "algo ok" << endl;}int run(Env& env) {//在此写入你的代码//env.get_data() 会返回当前数据流中的数据//env.done() 表示数据流是否输出完毕if (Puzzle == 1) {Solution1(env);} else if (Puzzle == 2) {Solution2(env);}return 0;}
};int main() {Env* env;for (int i = 0; i != FileNum + 1; i++) {if (Puzzle == 1 && i == 3) {break;}if (Puzzle == 2 && i == 0) {i = 3;}env = new Env(to_string(i));Algo algo;time_t start = clock();algo.run(*env);time_t end = clock();cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;cout << "占用内存：" << sizeof(algo) << " byte" << endl << endl;delete env;cout << endl;}system("pause");return 0;
}