一个C++ list问题?
list<VideoMessage> cache_Videos; //无序 不连续 视频缓存区;
struct VideoMessage
{
int VideoId; // Video帧序 [1 -n]
void * VideoContent; //内容;
}
现在有List<int> getVideoIds ;有序连续链表,存储等待载入缓存区cache_Videos的VideoId值信息;
求一算法,
如果缓存区cache_Videos中已经缓存getVideoIds中的A视频,则不需要重新getContent();
否则,如果缓存区cache_Videos没有getVideoIds中的A视频,需要调用getContent(); 获取void * VideoContent; //内容 存入缓存区cache_Videos中;
如果缓存区cache_Videos存有多余[即getVideoIds不需要的视频]则移除;
求时间复杂度O[n]的算法