As part of enhancing a music streaming platform's user experience, implement a feature that ranks songs by their popularity. Given n users and m songs, each user i has a preference list, pref[i], which is a permutation of numbers 0 to m-1, indicating the user's preference for a song. If a < b, the user prefers song pref[i][a] over song pref[i][b].
To rank the songs, use the following approach. Song x is said to beat song y if x is preferred over y by more than half of the users or if exactly half of the users prefer x over y, and x has a smaller id. Song x is considered more popular than song y if x beats more songs than y. If x and y beat the same number of songs, select the song with a lower id.
Example 1:
Input: n = 3, m = 3, pref = [[0, 1, 2], [0, 2, 1], [1, 2, 0]]
Output: [0, 1, 2]
Explanation:User Song Preference
0 Song 0 > Song 1 > Song 2
1 Song 0 > Song 2 > Song 1
2 Song 1 > Song 2 > Song 0
Comparisons:
Song Pair Users who prefer
Song 0 > Song 1 0, 1
Song 0 > Song 2 0, 1
Song 1 > Song 2 0, 2
It is established that Song 0 > Song 1 > Song 2. Hence the answer is [0, 1, 2].
🐭input:
output: