高频单词.md

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 692. 前K个高频单词
 */
 // root: i
 // left: 2*i + 1
 // right: 2*i + 2
 // Math.floor(n-1)/2 => root 索引
 // 堆顶放频率最低，字典序更小的
 class Heap {
     constructor(n, map) {
         // map 每个单词的出现频率
         // n 为前几个, 堆的长度
         this.arr = []; // 堆 数组
         this.max = n; // 堆的最大长度是n;
         this.map = map;
     }
     add(word) {
         let arr = this.arr;
         let len = arr.length;
         // 堆里添加单词
         // 还没到最大限度
         if (len < this.max) {
             this.directAdd(word);
             this.rebuild();
         } else {
             const newWordIsMoreFrequent = !this.compareLow(word, arr[0]);
             if (newWordIsMoreFrequent) {
                 this.arr[0] = word;
                 this.rebuild();
             }
         }
     }
     directAdd(word) {
         this.arr.push(word)
     }
     swap(i, j) {
         let arr = this.arr;
         [arr[i], arr[j]] = [arr[j], arr[i]];
     }
     rebuild() {
         let arr = this.arr;
         let len = arr.length;
         let i = Math.floor((len-1)/2);
         while(i >= 0) {
             let l = 2*i + 1;
             let r = 2*i + 2;
             let root = arr[i];
             let left = arr[l];
             let right = arr[r];
             let temp = i;
             let tempWord = root;
             if (l < len && this.compareLow(left, tempWord)) {
                 tempWord = left;
                 temp = l;
             }
             if (r < len && this.compareLow(right, tempWord)) {
                 tempWord = right;
                 temp = r;
             }
             if (temp !== i) {
                 this.swap(temp, i);
             }
             i--;
         }
     }
     compareLow(newWord, oldWorld) {
         let map = this.map;
         if (map[newWord] < map[oldWorld]) {
             return true;
         }
         if (map[newWord] > map[oldWorld]) {
             return false;
         }
         if (map[newWord] === map[oldWorld]) {
             return newWord > oldWorld;
         }
     }
     sort() {
         let map = this.map;
         this.arr.sort((prev,next) => {
             if (map[prev] > map[next]) {
                 return -1;
             }
             if (map[prev] < map[next]) {
                 return 1;
             }
             if (map[prev] === map[next]) {
                 return prev > next ? 1 : -1;
             }
         })
     }
     get result() {
         this.sort();
         return this.arr;
     }
 }
var topKFrequent = function(words, k) {
    let map = []; // 记录单词的出现频率
    words.forEach(word => {
        map[word] = map[word] === undefined ? 1 : map[word] + 1;
    })
    let heap = new Heap(k, map);
    let wordList = Object.keys(map);
    for(let i = 0; i < wordList.length; i++) {
        heap.add(wordList[i])
    }
    return heap.result;
};





/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 692. 前K个高频单词
 */
 // root: i
 // left: 2*i + 1
 // right: 2*i + 2
 // Math.floor(n-1)/2 => root 索引
 // 堆顶放频率最低，字典序更小的

var topKFrequent = function(words, k) {
    let ans = [];
    let wordsArr = words.sort(function(s, t) {  
        let a = s.toLowerCase();  
        let b = t.toLowerCase();  
        if (a < b) return -1;  
        if (a > b) return 1;  
        return 0;  
    })  
    console.log('wo', wordsArr)
    let map = new Map();
    let count = 0
    for (let i = 0; i < words.length; i++) {
        let select = words[i];
        if (!map.get(select)) {
            map.set(select, count + 1)
            count = 0
        } else {
            map.set(select, map.get(select) + 1)
        }
    }
    let arr = [...map];
    console.log(map, 'maparr', arr)
    arr.sort(function(a,b){ return b[1] - a[1] })
    console.log(arr, 'arr')
    for(let i = 0; i < k; i++) {
        ans.push(arr[i][0]);
    }
    console.log(ans)
    return ans;
};