algorithm - 根据我的要求为歌曲播放站设计一个类的更好的数据结构是什么？

Question

我必须为“公制”系统提出类和数据结构设计，以确定*乐队的顶级歌曲。

该类应该有两个 Web 服务调用

void play(String bandname, String songname);/*This method has to play song with the requested brandname and songname. Also have to keep track of the song payed count to support the below method.*/

String topSong(String bandname);/* This method has to play mostly played song under the requested brand*/

Sample inputs:
BrandName:"Lady Gaga", Song : "Pokerface";
BrandName:"Lady Gaga", Song : "Pokerface";
BrandName:"Lady Gaga", Song : "Alejandro";
BrandName:"Bruno Mars",Song : "Treasure";

请指教！

Answer 1

如果我理解正确，您需要维护一个字典，其中键是乐队名称，值是优先级队列。优先队列中的每个对象都将具有“歌曲名称”和“播放次数”属性，优先队列需要按“播放次数”属性排序。每次播放一首歌曲时，增加它的播放计数并堆积队列。

执行上述操作有点复杂，并且基于编程语言，实现方法可能会有很大差异。除非乐队的歌曲数量很大，否则您不应该这样做，这不太可能。

无论如何，这是实际的实现细节。此类问题的教科书答案始终是优先队列。

Answer 2

你需要两个存储。

1. 映射bandname到其顶部的字典songname。让我们称之为topBandSong。
2. 映射(bandname, songname)到这首歌的播放次数的字典。让我们称之为bandSongPopularity。

这topSong很简单（撇开对乐队一无所知的情况）：

Map<String, String> topBandSong = new HashMap();
String topSong(String bandname) {
    return topBandSong.get(bandname);
}

该play函数必须更新两个地图。这真的很容易：

Map<String, BigInteger> bandSongPopularity = new HashMap();
void play(String bandname, String songname) {
    /* First update bandSongPopularity */
    String k = bandname + "\000" + songname;
    BigInteger popularity = bandSongPopularity.get(k);
    if (popularity == null) {
        popularity = BigInteger.valueOf(1);
    }
    else {
        popularity = popularity.add(BigInteger.valueOf(1));
    }
    bandSongPopularity.put(k, popularity);
    /* then update topBandSong */
    String top = topSong(bandname);
    if (top == null) {
        topBandSong.put(bandname, songname);
    }
    else {
        String topK = bandname + "\000" + top;
        BigInteger topPopularity = bandSongPopularity.get(topK);
        /* topPopularity can not be NULL */
        if (popularity.compareTo(topPopularity) > 0) {
            topBandSong.put(bandname, songname);
        }
    }
    /* Finally really play this song. But this is left as an exercise ;-) */
}

复杂性是您选择的基础字典之一，即树或散列。

请注意，代码保留字符编号 0。

Answer 3

如果保存在内存中，这看起来像是哈希表、关联数组或字典的工作。如果保存在持久存储中，数据库将是最简单的方法。