[B] [C] [D]

Given a string, sort the characters in the string in descending order by frequency of occurrence.

Example 1:

Input: "tree" Output: "eert" Explanation: 'e' appears twice, 'r' and 't' both appear only once. So 'e' must come before 'r' and 't'. In addition, "EETR" is also a valid answer.Copy the code

Example 2:

Input: "ccCAaa" Output: "ccCAaa" Explanation: 'c' and 'a' both occur three times. Also, "aaaccc" is a valid answer. Note that "cacaca" is incorrect because the same letters must be placed together.Copy the code

Example 3:

Input: "Aabb" Output: "bbAa" Explanation: In addition, "bbAa" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'A' are considered two different characters.Copy the code

Their thinking

To order the input string in descending order of occurrence frequency, you need to get what characters appear in the string and how many times they appear. At this stage we can iterate over the input string and store the results using Map. Given the above results, there are two ways to solve the problem: \

sort

Convert the above results into an array, then sort them in descending order according to the number of character occurrences, and assemble the result string according to the descending order array results.

Code implementation

Var frequencySort = function(s) {const map = new map (); var frequencySort = function(s) {const map = new map (); for(let i = 0; i<s.length; I++) {if (map) from the (s) [I]) {map. The set (s [I], map. Get [I] (s) + 1)} else {map. The set (s [I], 1)}} / / the results into a const array storage arr = []; Map.foreach ((val,key) => {arr.push({val,key})}) // Sort arr.sort((a,b) => b.val-a.val) // assemble the result string let from the sorted array res = ''; for(let i = 0; i<arr.length; i++){ res += arr[i].key.repeat(arr[i].val) } return res; };Copy the code

Big pile top

Anything that involves maintaining maximum values can be done with the heap. Here, because you want to maintain the most frequently occurring characters, you need a large top heap. Insert each group of data obtained above into the big top heap, and take advantage of the nature of the big top heap, the top element of the heap is the character that occurs most frequently in the remaining characters. Then assemble the resulting string based on each fetch of the heap top elements.

Code implementation

Constructor (){this.arr = []; // Constructor (){this.arr = []; this.size = 0; } // Insert operation push(item){this.arr.push(item); this.size++; If (this.size>1){let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.arr[parent].val<this.arr[cur].val){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; }}} / / pop operation pop () {if (this. Size = = = 1) {this. Size = 0; return this.arr.pop(); } const res = this.arr[0] this.arr[0] = this.arr.pop(); this.size--; // let cur = 0,childl = 1,childr = 2; while( (childl<this.size&&this.arr[cur].val<this.arr[childl].val) || (childr<this.size&&this.arr[cur].val<this.arr[childr].val) ){ if(childr<this.size&&this.arr[childl].val<this.arr[childr].val){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]]  cur = childl; } childl = cur*2+1,childr = cur*2+2; } return res; }} var frequencySort = function(s) {const map = new map (); for(let i = 0; i<s.length; I++) {if (map) from the (s) [I]) {map. The set (s [I], map. Get [I] (s) + 1)} else {map. The set (s [I], 1)}} / / create instances const dading heap heap = new BigHeap ();  ForEach ((val,key) => {heap.push({val,key})}) while(heap.size){ const item = heap.pop(); res += item.key.repeat(item.val) } return res; };Copy the code

At this point we are done with Leetcode-451 – sorting by character frequency

If you have any questions or suggestions, please leave a comment!