0

我的问题是正确排序的逻辑——按字母顺序。我只是不知道我可以使用什么技术来保持最多位于顶部的值以及它们是否具有相同的出现并按字母顺序返回列表。

输入：["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出：["i", "love"] 解释："i" and "love "是最常用的两个词。请注意，由于字母顺序较低，“i”出现在“love”之前。

var topKFrequent = function(words, k) {
    // Intialize a map to obtain our frequency of words
    const wordCount = {}; 
    for (const word of words)  {
        wordCount[word] = (wordCount[word] || 0) + 1
    }
    const priority = new PriorityQueue();
    
    for (const word in wordCount) {
        priority.enqueue(word, wordCount[word])
        if (priority.values.length > k) {
            priority.dequeue();
        }
    }
    const result = []; 
    for (const node of priority.values) {
        result.push(node.val)
    }
  
    return result; 
};


function stringCompare(word1, word2) {
    if (word1.priority === word2.priority) return word2.val.localeCompare(word1.val); 
    return word1.priority - word2.priority; 
}



class PriorityQueue {
  constructor() {
    this.values = []; 
  }

  enqueue(val, priority) {
    let node = new Node(val, priority);
    this.values.push(node); 
    this.bubbleUp();  
  }

  bubbleUp() {
    let currentIdx = this.values.length - 1
    const child = this.values[currentIdx]; 
    while (currentIdx > 0) {
      let parentIdx = Math.floor((currentIdx - 1) / 2); 
      const parent = this.values[parentIdx]; 
      if (child.priority >= parent.priority) break; 
      // Swap 
      this.values[currentIdx] = parent; 
      this.values[parentIdx] = child; 
      currentIdx = parentIdx; 
    }
  }

  dequeue() {
    const min = this.values[0]; 
    const end = this.values.pop(); 
    if (this.values.length > 0) {
      this.values[0] = end; 
      this.sinkDown(); 
    }
    return min; 
  }



  sinkDown() {
    let idx = 0; 
    const currentElement = this.values[0]; 
    const { length } = this.values; 

    while (true) {
      let leftChildIdx = 2 * idx + 1; 
      let rightChildIdx = 2 * idx + 2; 
      let leftChild, rightChild; 
      let toSwapIdx = null; 

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx]; 
        if (leftChild.priority < currentElement.priority) {
          toSwapIdx = leftChildIdx; 
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx]; 
        if (
          (toSwapIdx === null && rightChild.priority < currentElement.priority) || 
          (toSwapIdx !== null && rightChild.priority < leftChild.priority)
          ) {
            toSwapIdx = rightChildIdx; 
        }
      }
      if (toSwapIdx === null) break;// break while loop condition
      this.values[idx] = this.values[toSwapIdx]; 
      this.values[toSwapIdx] = currentElement; 
      idx = toSwapIdx; 
    }
  }



}


class Node {
  constructor(val, priority) {
    this.val = val; 
    this.priority = priority; 
  }
}

4

1 回答 1

0

您可以使用数组方法，包括.filter(),.map()等来简化您的代码。我希望这个解决方案能满足要求。

我的解决方案

function myFunction(words, k) {
  return [...new Set(words.map(word => words.filter(e => e === word)).sort((a, b) => b.length - a.length).filter(e => e.length > 1).map(e => e[0]))]
            .slice(0, k)
            .sort();
}

console.log(myFunction(["love", "i", "leetcode", "love", "i", "coding"], 2));
// Output: ["i", "love"] 

console.log(myFunction(["i", "need", "you", "i", "love", "you", "i", "hate", "you"], 3));
// Output: ["i", you"] 

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 4));
// Output: ["else", "if"]

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 2));
// Output: ["else", "if"]

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 2));
// Output: ["else", "if"]

一步一步看

上面的解决方案是一行代码，可能不可读。我已将其拆分以使其易于理解。

function myFunction(words, k) {
  console.log("--- Start ---");
  let arr = [];
  
  arr = words.map(word => words.filter(e => e === word));
  console.log(`Step 1: ${arr}`);
  
  arr = arr.sort((a, b) => b.length - a.length);
  console.log(`Step 2: ${arr}`);
  
  arr = arr.filter(e => e.length > 1);
  console.log(`Step 3: ${arr}`); 
  
  arr =  arr.map(e => e[0]);
  console.log(`Step 4: ${arr}`);
  
  arr = [...new Set(arr)]; 
  console.log(`Step 5: ${arr}`);
  
  arr = arr.slice(0, k);
  console.log(`Step 6: ${arr}`);
  
  arr = arr.sort();
  console.log(`Step 7: ${arr}`);
  
  console.log("--- Completed ---");
  return arr
}

console.log(myFunction(["love", "i", "leetcode", "love", "i", "coding"], 2));
// Output: ["i", "love"] 

console.log(myFunction(["i", "need", "you", "i", "love", "you", "i", "hate", "you"], 3));
// Output: ["i", you"] 

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 4));
// Output: ["else", "if"]

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 2));
// Output: ["else", "if"]

console.log(myFunction(["if", "else if", "else", "if", "if", "if", "else"], 2));
// Output: ["else", "if"]

于 2021-03-03T19:35:44.003 回答