Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

451. Sort Characters By Frequency #175

Open
Tcdian opened this issue May 22, 2020 · 1 comment
Open

451. Sort Characters By Frequency #175

Tcdian opened this issue May 22, 2020 · 1 comment

Comments

@Tcdian
Copy link
Owner

Tcdian commented May 22, 2020

451. Sort Characters By Frequency

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

Example 1

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
@Tcdian
Copy link
Owner Author

Tcdian commented May 22, 2020

Solution

  • JavaScript Solution
/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const cache = new Map();
    let result = '';
    for (let i = 0; i < s.length; i++) {
        cache.set(s[i], (cache.get(s[i]) || 0) + 1);
    }
    const pairs = [...cache.entries()];
    pairs.sort(([,a], [,b]) => b - a);
    for (let i = 0; i < pairs.length; i++) {
        const [char, count] = pairs[i];
        for (let n = 0; n < count; n++) {
            result += char;
        }
    }
    return result;
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant