347_Top_K_Frequent_Elements

qiyuangong · qiyuangong · commit 303f50587898 · 2018-12-01T22:58:15.000+08:00
diff --git a/README.md b/README.md
@@ -112,6 +112,7 @@ Also, there are open source implementations for basic data structs and algorithm
 | 339 | [Nested List Weight Sum](https://leetcode.com/problems/nested-list-weight-sum/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/339_Nested_List_Weight_Sum.py) | Depth-first recursion |
 | 340 | [Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/340_Longest_Substring_with_At_Most_K_Distinct_Characters.py) | Maintain a sliding window with at most k distinct characters and a count for this window. Note that the start position need a loop to update.|
 | 346 | [Moving Average from Data Stream](https://leetcode.com/problems/moving-average-from-data-stream/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/346_Moving_Average_from_Data_Stream.py) | fix-sized queue or dequeue, O(1) and O(n) |
+| 347 | [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/347_Top_K_Frequent_Elements.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/347_Top_K_Frequent_Elements.java) | Sort by frequency, O(nlogn) and O(n). |
 | 351 | [Android Unlock Patterns](https://leetcode.com/problems/android-unlock-patterns/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/351_Android_Unlock_Patterns.py) | Backtracking, O(n!) and O(n) |
 | 359 | [Logger Rate Limiter](https://leetcode.com/problems/logger-rate-limiter/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/359_Logger_Rate_Limiter.py) | 1. hash which stores the latest timestamp, O(1) and O(n)<br>2. Using Priority queue to remove older logs, O(n) and O(n) |
 | 366 | [Find Leaves of Binary Tree](https://leetcode.com/problems/find-leaves-of-binary-tree/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/366_Find_Leaves_of_Binary_Tree.py) | 1. Set or hash to check leaft, O(n^2) and O(n)<br>2. Recursively check level and return them, O(n) and O(n)|
@@ -151,7 +152,7 @@ Also, there are open source implementations for basic data structs and algorithm
 | 617 | [Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/617_Merge_Two_Binary_Trees.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/617_Merge_Two_Binary_Trees.java) | Traverse both trees Recursion & Iterative (stack) |
 | 654 | [Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/654_Maximum_Binary_Tree.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/654_Maximum_Binary_Tree.java) | 1. Divide and conquer, recursive, O(n^2)<br>2. Monotonic stack, O(n) |
 | 697 | [Degree of an Array](https://leetcode.com/problems/degree-of-an-array/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/697_Degree_of_an_Array.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/697_Degree_of_an_Array.java) | 1. Find degree and value, then find smallest subarray (start and end with this value), O(n) and O(n)<br>2. Go through nums, remember left most pos and right most for each value, O(n) and O(n) |
-| 706 | [Design HashMap](https://leetcode.com/problems/design-hashmap/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/706_Design_HashMap.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/@706_Design_HashMap.java) | Hash implementation, mod is fine. Be careful about key conflict and key remove. |
+| 706 | [Design HashMap](https://leetcode.com/problems/design-hashmap/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/706_Design_HashMap.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/706_Design_HashMap.java) | Hash implementation, mod is fine. Be careful about key conflict and key remove. |
 | 709 | [To Lower Case](https://leetcode.com/problems/to-lower-case/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/709_To_Lower_Case.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/709_To_Lower_Case.java) | String processing:<br>1. str.lower() or str.toLowerCase()<br>2. ASCII processing. O(n) and O(1) |
 | 716 | [Max Stack](https://leetcode.com/problems/max-stack/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/716_Max_Stack.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/716_Max_Stack.java) | 1. Two stacks<br> 2. Double linked list and Hash |
 | 720 | [Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/720_Longest_Word_in_Dictionary.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/720_Longest_Word_in_Dictionary.java) | 1. Brute Force, O(sum(w^2)) and O(w)<br>2. Tire Tree, O(sum(w) and O(w))<br>3. Sort and word without last char, O(nlogn + sum(w)) and O(w) |
diff --git a/java/347_Top_K_Frequent_Elements.java b/java/347_Top_K_Frequent_Elements.java
@@ -0,0 +1,27 @@
+class Solution {
+  public List<Integer> topKFrequent(int[] nums, int k) {
+    // build hash map : character and how often it appears
+    HashMap<Integer, Integer> count = new HashMap();
+    for (int n: nums) {
+      count.put(n, count.getOrDefault(n, 0) + 1);
+    }
+
+    // init heap 'the less frequent element first'
+    PriorityQueue<Integer> heap =
+            new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));
+
+    // keep k top frequent elements in the heap
+    for (int n: count.keySet()) {
+      heap.add(n);
+      if (heap.size() > k)
+        heap.poll();
+    }
+
+    // build output list
+    List<Integer> top_k = new LinkedList();
+    while (!heap.isEmpty())
+      top_k.add(heap.poll());
+    Collections.reverse(top_k);
+    return top_k;
+  }
+}
diff --git a/python/347_Top_K_Frequent_Elements.py b/python/347_Top_K_Frequent_Elements.py
@@ -0,0 +1,10 @@
+class Solution(object):
+    def topKFrequent(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: List[int]
+        """
+        counter = collections.Counter(nums)
+        return [k for k,v in counter.most_common(k)]
+        # return heapq.nlargest(k, count.keys(), key=count.get) 
diff --git a/python/374_Guess_Number_Higher_or_Lower.py b/python/374_Guess_Number_Higher_or_Lower.py
@@ -19,4 +19,4 @@ def guessNumber(self, n):
             elif res > 0:
                 begin = mid + 1
             else:
-                end = mid - 1
+                end = mid - 1
