Leetcode 347 - Find k most frequent numbers in the array - C++/ Java Solutions

July 28, 2016

Find k most frequent numbers in the array
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]

Code study:    nothing can compare to code reading 
C++ code to study: 
use unordered_map and priority_queue
1. https://gist.github.com/jianminchen/cd9f536708f6ec42ae229d853c881361

2. use bucket sort - 
https://gist.github.com/jianminchen/c3d49c11c090b91c94ae7b05bdc11786

https://gist.github.com/jianminchen/88f3e2d441c62ecb7d9d706d1b9bda37

3. use Map + std::sort
https://gist.github.com/jianminchen/3e5bba61847c5c84d95e1ca7806c81be

Java code to study:

1.use a min-heap - Java PriorityQueue class - underneath heap sort 
https://gist.github.com/jianminchen/76b2b3196a4e58312e1ba1d0c288d941

2. use heap:
https://gist.github.com/jianminchen/2482dbacb59e464d94c4a4d16cbc6d3b

3. use bucket sort:
https://gist.github.com/jianminchen/0626a0cb673526d4b7b58698004b87b8

4. use Collections.sort - underneath merge sort, 
https://gist.github.com/jianminchen/3d8fab01965efd19a0f72b2109501c8d

5. use quicksort partition

https://gist.github.com/jianminchen/99d2dea800b28e24456827946409d32d

Conclusion: Based on the analysis, the time complexity should be better than O(nlogn), if using heap sort or merge sort, when k is big enough close to n, then, O(nlogk) is close to O(nlogn). 

However, the bucket sort is always O(n), so the time complexity is O(n), no matter k's size.