A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.
You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:
- Adding scenic locations, one at a time.
- Querying the
ithbest location of all locations already added, whereiis the number of times the system has been queried (including the current query).- For example, when the system is queried for the
4thtime, it returns the4thbest location of all locations already added.
- For example, when the system is queried for the
Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.
Implement the SORTracker class:
SORTracker()Initializes the tracker system.void add(string name, int score)Adds a scenic location withnameandscoreto the system.string get()Queries and returns theithbest location, whereiis the number of times this method has been invoked (including this invocation).
Example 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
<strong>Input</strong> ["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"] [[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []] <strong>Output</strong> [null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"] <p><strong>Explanation</strong> SORTracker tracker = new SORTracker(); // Initialize the tracker system. tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system. tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system. tracker.get(); // The sorted locations, from best to worst, are: branford, bradford. // Note that branford precedes bradford due to its <strong>higher score</strong> (3 > 2). // This is the 1<sup>st</sup> time get() is called, so return the best location: "branford". tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system. tracker.get(); // Sorted locations: branford, alps, bradford. // Note that alps precedes bradford even though they have the same score (2). // This is because "alps" is <strong>lexicographically smaller</strong> than "bradford". // Return the 2<sup>nd</sup> best location "alps", as it is the 2<sup>nd</sup> time get() is called. tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system. tracker.get(); // Sorted locations: branford, alps, bradford, orland. // Return "bradford", as it is the 3<sup>rd</sup> time get() is called. tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system. tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland. // Return "bradford". tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system. tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland. // Return "bradford". tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland. // Return "orland". </p> |
Constraints:
nameconsists of lowercase English letters, and is unique among all locations.1 <= name.length <= 101 <= score <= 105- At any time, the number of calls to
getdoes not exceed the number of calls toadd. - At most
4 * 104calls in total will be made toaddandget.
Solution: TreeSet w/ Iterator
Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.
Time complexity: add O(logn) / get O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class SORTracker { public: SORTracker() {} void add(string name, int score) { if (*s.emplace(-score, name).first < *cit) --cit; } string get() { return (cit++)->second; } private: set<pair<int, string>> s; // Note: cit points to begin(s) after first insertion. set<pair<int, string>>::const_iterator cit = end(s); }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment