力扣347——前 K 個高頻元素

2020 年 2 月 19 日
筆記

這道題主要涉及的是對數據結構里哈希表、小頂堆的理解，優化時可以參考一些排序方法。

原題

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2  輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1  輸出: [1]

說明：

你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
你的算法的時間複雜度必須優於 O(n log n) , n 是數組的大小。

原題url：https://leetcode-cn.com/problems/top-k-frequent-elements/

解題

正常思路

為了解決這道題，我們首先需要知道每個元素出現的次數。最方便的話，可以使用哈希表，因為這就是一個數字——出現次數的映射關係。此處的時間複雜度為O(n)

其次，因為需要查找頻率前 k 高的元素，所以我們肯定是需要排序的，時間複雜度為O(n log n)的排序方法有許多，快速排序、堆排序等，我是用的堆排序，使用小頂堆，這樣在每次入堆的時候，檢查一下堆的個數是否超過 k，如果超過，則移除堆頂的元素(也就是次數最少的元素)。

這樣堆里剩餘的元素也就是最終的結果了，接下來我們看看代碼：

class Solution {        public List<Integer> topKFrequent(int[] nums, int k) {          // 構建hashMap，記錄每個元素出現的個數          Map<Integer, Integer> countMap = new HashMap<>();          for (int num : nums) {              countMap.put(num, countMap.getOrDefault(num, 0) + 1);          }            // 利用PriorityQueue構建小頂堆          PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> countMap.get(n1) - countMap.get(n2));          Set<Integer> keySet = countMap.keySet();          for (int key : keySet) {              heap.add(key);              // 如果個數大於k，則移除次數最少的數              if (heap.size() > k) {                  heap.poll();              }          }            List<Integer> result = new LinkedList<>();          Iterator<Integer> iterator = heap.iterator();          while (iterator.hasNext()) {              result.add(iterator.next());          }            return result;      }  }

提交OK。

桶排序優化

針對排序，我想到了一個優化，利用桶排序，其時間複雜度為O(n)，主要是浪費空間，因為需要申請額外的數組，下標代表出現的次數，元素我用的是 LinkedList，這樣可以存儲多個。那麼這個在進行輸出時，只要從後往前進行遍歷，當結果的數量達到 k 時，就可以停止了。

接下來我們看看代碼：

class Solution {        public List<Integer> topKFrequent(int[] nums, int k) {          // 構建hashMap，記錄每個元素出現的個數          Map<Integer, Integer> countMap = new HashMap<>();          // 記錄最多的次數          int maxCount = 0;          for (int num : nums) {              int count = countMap.getOrDefault(num, 0) + 1;              if (count > maxCount) {                  maxCount = count;              }              countMap.put(num, count);          }            // 桶排序，構建數組，下標為重複的次數          LinkedList[] array = new LinkedList[maxCount + 1];          for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {              int key = entry.getKey();              int count = entry.getValue();              LinkedList<Integer> list = array[count];              if (list == null) {                  list = new LinkedList<>();                  array[count] = list;              }              list.add(key);          }            // 倒着遍曆數組，直到找到K個元素          List<Integer> result = new LinkedList<>();          for (int i = array.length - 1; i >= 0 && result.size() < k; i--) {              List<Integer> list = array[i];              if (list == null) {                  continue;              }                result.addAll(list);          }            return result;      }  }

提交OK。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是對數據結構的理解，優化時可以參考一些特殊的排序方法。