初识算法——队列

第一个版本 复杂度O(m*n)

主要思路

先用一个数组读入所有输入

再遍历该数组

用一个数组记录遍历的数字是否出现过，利用剩余集控制空间

易错点

1. 如何控制空间，尤其是超限后如何覆盖

#include <iostream>
using namespace std;
int fun(const int* p, int m, int n) {
    int ret = 0;    
    int capacity[m];		//定义一个数组用来记录读入的数是否出现过
    for(int i = 0; i < m; i++) 
        capacity[i] = -1;
    int index = 0;
    for(const int* s = p; s < p + n; s++) {			//遍历所有读入的数
        for(int i = 0; i < m; i++) {		//遍历有限的内存空间
            if(*s == capacity[i]) {			//如果读入的数之前读到过
                continue;
            }
        }
        //如果读入的数之前没读过
        capacity[index % m] = *s;			//这步是这个方法的灵魂，因为内存有限，内存中数不需要考虑顺序，所以利用模的剩余集的知识,即任意数 %m 结果均在0 ~ m-1范围
        
        index++;
        ret++;
    }
    return ret;
}
int main() {
    int capacity, VocabularyNumber;
    cin >> capacity >> VocabularyNumber;
    int article[VocabularyNumber];
    for(int i = 0; i < VocabularyNumber; i++)
        cin >> article[i];
    cout << fun(article, capacity, VocabularyNumber) << endl;
    return 0;
}

第二版，涉及到队列思想，复杂度为O(n)

主要思路

1. 如果前面n个数字没有重复，那么有限内存中最终留下的是最后输入的m个数字，所以可以想象一大一小两张纸条，“大纸条”里有新数字进来则且“小纸条”已满则“小纸条”向后移动
2. haveThisNumberAppear数字的下标记录的是读入的数字，内部存储的值（0或1）表示的是该数字是否在内存中

易错点

1. 要先判断数字是否重复
2. 只有++count才能把读入的数字放到下一位，count++会覆盖当前位数字
3. 将最早进入内存的数字从内存中移除时，应该

#include <iostream>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    int x;
    int haveThisNumberAppear[1010] = {0};		//记录读入的数字是否在内存中
    int internalStorage[1010];			//有限内存
    int count = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d",&x);
        if(haveThisNumberAppear[x] == 1)		//先判断这个数字有没有出现过
            continue;
        else {
            if(count < m) {					//如果内存没有满
                 haveThisNumberAppear[x] = 1;		//先记录该数字已在内存
                 internalStorage[++count] = x;     //再在下一位记录该数字，注意是下一位！！！若是count++则会覆盖当前位置
            }
            else {						//如果内存满了
                 haveThisNumberAppear[x] = 1;		//先记录该数字已在内存
                 haveThisNumberAppear[internalStorage[count - m + 1]] = -1;		//将最早进入内存的数字从内存中移除，与下一步共同实现了将“小纸条”往后移一位
                 internalStorage[++count] = x;		//再在下一位记录该数字
            }
        }
    }
    cout << count << endl;
    return 0;
}