[吐槽] Find k Most Frequent Number

Problem:

  // nums = [5, 3, 1, 1, 1, 3, 73, 1]

  // k = 1

  // return [1]

  

  // k = 2 

  // return [1, 3]

  

  // k = 3

  // return [1, 3, 5]

Thinking:

Pocket Gems果然是面那两道原题，后悔之前没有把Find k most frequent number写一写，现场整出这么一个 O(N^2logN) 的解法……额……

Java Code :

  public int[] getKthFrequent(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k > nums.length) {
      return null;
    }
    
    int[] result = new int[k];
    Queue<Node> queue = new PriorityQueue<Node>(k, new Comparator<Node>(){
      public int compare(Node A, Node B) {
        return A.frequency - B.frequency;
      }
    }); //N[1, 4] N[3, 2] N[5, 1] N [73, 1]
    
    Arrays.sort(nums); // O(NlogN)
    
    int pre = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {//O(N)
      if (nums[i] == pre) {
        count++;
      } else {
        Node node = new Node(pre, count);
        queue.add(node);//O(NlogN)
        pre = nums[i];
        count = 1;
      }
    }// O(N^2logN)
    
    for (int i = 0; i < k; i++) {
      result[i] = queue.poll().number;
    }//O(N)
    
    return result;
    
  }

class Node {
  int number;
  int frequency;
  
  Node(int number, int frequency) {
    this.number = number;
    this.fequency = frequency;
  }
}