我尝试在 TestDome 上做一个关于发现播放列表是否有重复的练习(TestDome C++ Playlist)
我试过这样解决:
bool isRepeatingPlaylist()
{
std::map<std::string, int> songs;
Song* pSong = this;
while (pSong != nullptr) {
if (songs[pSong->name] > 0)
return true;
songs[pSong->name]++;
pSong = pSong->nextSong;
}
return false;
}
反馈是我通过了4个测试用例中的3个。我没有通过的测试用例是关于性能的。你能帮我改进吗?
第四个测试是“大型播放列表的性能测试” 当涉及到效率并且您不需要有序数据时,您应该使用 unordered_set<> 或 unordered_map<>。
map<> 搜索复杂度为 O(log n),但在 unordered_set<> 或 unordered_map<> 的最坏情况下平均为 O(1) 到 O(n)。
以下代码通过了 TestDome C++ Playlist 的所有 4 个测试
bool isRepeatingPlaylist()
{
std::unordered_set<std::string> playedSongs;
Song *pSong = this;
while (pSong != nullptr)
{
if (playedSongs.find(pSong->name) == playedSongs.end())
playedSongs.insert(pSong->name);
else
return true;
pSong = pSong->nextSong;
}
return false;
}
使用它只需添加#include
此解决方案使用标准环路检测算法并通过所有测试:
bool isInRepeatingPlaylist()
{
Song *p1 = this;
Song *p2 = this;
do {
p1 = p1->nextSong;
if(p2->nextSong != nullptr) {
p2 = p2->nextSong->nextSong;
} else {
break;
}
if(p1 == p2) return true;
} while(p1 != nullptr && p2 != nullptr);
return false;
}