【Day 20 】2021-12-31 - 347. 前 K 个高频元素

[azl397985856]

347. 前 K 个高频元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/top-k-frequent-elements/

前置知识

• 哈希表
• 堆排序
• 快速选择

  题目描述

  
  给定一个非空的整数数组，返回其中出现频率前  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  是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/top-k-frequent-elements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[CodeFarmersWorld]

class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); }

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (int[] a, int[] b) -> a[1] - b[1]
);

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    int num = entry.getKey(), count = entry.getValue();
    if (pq.size() == k) {
        if (pq.peek()[1] < count) {
            pq.poll();
            pq.offer(new int[]{num, count});
        }
    } else {
        pq.offer(new int[]{num, count});
    }
}

int[] ans = new int[k];
for (int i = 0; i < k; i++) {
    ans[i] = pq.poll()[0];
}
return ans;

} }

[zzzpppy]

今天跨年就不写了，明天仔细看 ··· class Solution { public List topKFrequent(int[] nums, int k) { // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } // 遍历map，用最小堆保存频率最大的k个元素 PriorityQueue pq = new PriorityQueue<>(new Comparator() { @Override public int compare(Integer a, Integer b) { return map.get(a) - map.get(b); } }); for (Integer key : map.keySet()) { if (pq.size() < k) { pq.add(key); } else if (map.get(key) > map.get(pq.peek())) { pq.remove(); pq.add(key); } } // 取出最小堆中的元素 List res = new ArrayList<>(); while (!pq.isEmpty()) { res.add(pq.remove()); } return res; }

[WANGDI-1291]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

[rootdavid]

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
      unordered_map<int, int> map;

      for (int num : nums) map[num]++;

      int n = nums.size();

      vector<int> s(n + 1);

      for (auto& [k, v] : map) s[v]++;

      int i = n, t = 0;

      while (t < k) t += s[i--];

      vector<int> res;

      for (auto& [k, v] : map) {
        if (v > i) res.push_back(k);
      }

      return res;

    }
};

[fornobugworld]

思路：先排序，统计每个数的次数放在二维数组，再排序 时间复杂度O(nlogn)空间复杂度O(n) class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: nums.sort() pre = float(inf) ans = list() for i in nums: if i != pre: ans.append([0,i]) else: ans[-1][0] +=1 pre = i ans.sort(reverse =True) ansK = list() for j in range(k): ansK.append(ans[j][1]) return ansK

[Richard-LYF]

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = collections.Counter(nums) num_cnt = list(count.items()) topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1) return [item[0] for item in topKs]

def findTopK(self, num_cnt, k, low, high):
    pivot = random.randint(low, high)
    num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
    base = num_cnt[low][1]
    i = low
    for j in range(low + 1, high + 1):
        if num_cnt[j][1] > base:
            num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
            i += 1
    num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
    if i == k - 1:
        return num_cnt[:k]
    elif i > k - 1:
        return self.findTopK(num_cnt, k, low, i - 1)
    else:
        return self.findTopK(num_cnt, k, i + 1, high)

[Alfie100]

解题思路

哈希+排序。

Python 代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        dic = collections.defaultdict(int)
        for num in nums:
            dic[num] += 1

        lst = list(dic.items())
        lst.sort(key=lambda x: x[1], reverse=True)

        return [x[0] for x in lst[:k]]

复杂度分析

• 时间复杂度：O(nlogn)，其中 n 为数组长度。
• 空间复杂度：O(n)。

[Okkband]

/**

• @param {number[]} nums
• @param {number} k
• @return {number[]} */ var topKFrequent = function (nums, k) { let map = {}; for (let num of nums) { if (map[num] === undefined) { map[num] = 1; } else { map[num] += 1; } } return Object.entries(map).sort((a, b) => b[1] - a[1]).slice(0,k).map(i => i[0]) };

[machuangmr]

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[k];
        for (int num : nums) {
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
       int maxTime = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > maxTime) {
                maxTime = entry.getValue();
            }
        }

        while(k > 0) {
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (maxTime == entry.getValue()) {
                    res[k - 1] = entry.getKey();
                    k--;
                }
            }
             maxTime--;
        }
        return res;
    }
}

复杂度

• 时间复杂度O(nlogk)
• 空间复杂度O(n)

[for123s]

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct hashtable
{
    int value;
    int cnt;
};

int cmp(const void *a, const void *b)
{
    return *(const int *)a - *(const int *)b;
}

int cmph(const void *a, const void *b)
{
    return ((struct hashtable *)b)->cnt - ((struct hashtable *)a)->cnt;
}

int* topKFrequent(int* nums, int size, int k, int* returnSize) {
    if(k == 0 || size == 0){
        *returnSize = k;
        return 0;
    }
    if (size < k){
        *returnSize = 0;
        return 0;
    }
    if(size == k && k == 1){
        *returnSize = 1;
        return nums;    
    }

    int *ans = calloc(k, sizeof(int));
    struct hashtable hash[size];
    memset(hash,0,sizeof(struct hashtable)*size);
    int i;
    int count=1;
    *returnSize = k;
    qsort(nums, size,sizeof(int),cmp);

    hash[0].value=nums[0];
    hash[0].cnt++;

    for (i=1;i<size;i++){
        if(hash[count-1].value == nums[i]){
            hash[count-1].cnt++;
        } else {
            count++;
            hash[count-1].value = nums[i];
            hash[count-1].cnt++;
        }
    }

    qsort(hash, count,sizeof(hash[0]),cmph);

    for(i=0;i<k;i++){
        ans[i] = hash[i].value;
    }

    return ans;

}

[Davont]

code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 交换节点
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp;
    }
    // 获取父节点
    getParentIndex(i) {
        // return Math.floor((i - 1) / 2);
        return (i - 1) >> 1; // 2进制操作，取商
    }
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    // 上移
    shiftUp(index) {
        if (index == 0) { return; }
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) { // 父节点大于当前节点
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    // 下移操作
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    // 将值插入堆的底部，即数组的尾部。
    // 然后_上移:将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
    // 大小为k的堆中插入元素的时间复杂度为O(logK)
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    // 删除堆顶
    // 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)。
    // 然后下移:将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶。
    // 大小为k的堆中删除堆顶的时间复杂度为O(logK)。
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    peek() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}
var topKFrequent = function(nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    });
    const h = new MinHeap();
    map.forEach((value, key) => {
        h.insert({ value, key });
        if(h.size() > k) {
            h.pop()
        }
    })
    return h.heap.map(a => a.key);
};

[1149004121]

347. 前 K 个高频元素

思路

用哈希表保存数和期出现次数，然后按出现次数的大小从大到小排序，返回前k个。

代码

    var topKFrequent = function(nums, k) {
        let counts = {};
        for(let num of nums){
            counts[num] = (counts[num] || 0) + 1;
        };
        let pairs = Object.keys(counts).map((num) => [counts[num], num]);
        select(0, pairs.length -1, k - 1);
        return pairs.slice(0, k).map(item => item[1]);

        function select(start, end, offset){
            if(start >= end) return;
            let index = partition(start, end);
            if(index === offset) return;
            if(index <= offset){
                select(index + 1, end, offset);
            }else{
                select(start, index - 1, offset);
            }
        };
        function partition(left, right){
            let pivot = pairs[right][0];
            let cur = left;
            let leftPairIndex = left;
            while(cur < right){
                if(pairs[cur][0] > pivot){
                    swap(leftPairIndex++, cur);
                }
                cur++;
            }
            swap(leftPairIndex, right);
            return leftPairIndex;
        };
        function swap(x, y){
            let temp = pairs[x];
            pairs[x] = pairs[y];
            pairs[y] = temp; 
        }
    };

复杂度分析

• 时间复杂度：O(N^2)。
• 空间复杂度：O(N)。

[pf135145]

解题

用obj存储数字出现的次数，转换成数组并排序

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = {}
    let res = []
    let arr
    for (let i=0; i<nums.length; i++) {
        if (nums[i] in map) {
            map[nums[i]] ++
        } else {
            map[nums[i]] = 0
        }
    }
    for (let k in map) {
        res.push({
            key: k,
            val: map[k]
        })
    }
    arr = res.sort((a, b) => {
        return b.val - a.val
    }).map(o => {
        return Number(o.key)
    }).splice(0, k)
    return arr
};

[simbafl]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = dict()
        if not nums:
            return
        for num in nums:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1
        l = list(dic.items())
        l.sort(key= lambda x:x[1], reverse=True)

        res =[]
        for i in range(k):
            res.append(l[i][0])
        return res

[Jay214]

思路

hash map，排序

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let res = []
    const map = new Map()
    nums.forEach(v => {
        if (map.has(v)) {
            map.set(v, map.get(v) + 1)
        } else {
            map.set(v, 1)
        }
    })

    return Array.from(map.keys()).sort((a, b) => map.get(b) - map.get(a)).slice(0, k)
};

复杂度

时间O(nlg(n)) 空间O(n)，n为数组长度

[Myleswork]

思路

用hash记录元素出现次数，排序后取前k个输出

代码

class Solution {
public:
    struct Nums{
        int val;
        int count;
        Nums(int value,int count):val(value),count(count){};
    };

    static bool cmp(Nums a,Nums b){
        return a.count>b.count;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        vector<Nums> vec;
        for(int num:nums) hash[num]++;
        for(auto it = hash.begin();it!=hash.end();it++){
            vec.push_back(Nums(it->first,it->second));
        }
        sort(vec.begin(),vec.end(),cmp);
        vector<int> res;
        while(k--){
            res.push_back(vec[k].val);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

[q815101630]

Count + Min heap

• Count the frequency of each distinct element in the array
• Build a minHeap of size k by initializing the heap with the first k elements in the nums
• For other elements, if the count is larger than the top of the heap, push it and heapify (siftDown)

• the final heap is our desired answer

  
  class MinHeap:
  def __init__(self, num):
      self.heap = self.buildHeap(num)
  
  def buildHeap(self, arr):
      firstParent = (len(arr)-2)//2
      for i in range(firstParent, -1, -1):
          self.siftDown(i, len(arr), arr)
      return arr
  
  def siftDown(self, node, endIdx, arr):
      left = node*2+1 if node*2+1 < endIdx else -1
      while left != -1:
          right = left+1 if left+1 < endIdx else -1
          idxToSwap = right if arr[right] < arr[left] and right != -1 else left
          if arr[node] > arr[idxToSwap]:
              arr[node], arr[idxToSwap] = arr[idxToSwap], arr[node]
              node = idxToSwap
              left = node*2+1 if node*2+1 < endIdx else -1
          else:
              break
  def remove(self):
      heap = self.heap
      heap[0], heap[-1] = heap[-1], heap[0]
      ret = self.heap.pop()
      self.siftDown(0, len(heap), heap)
      return ret

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = collections.Counter(nums) arr = [(v,i) for i,v in cnt.items()]

    minHeap = MinHeap(arr[:k])

    for i in range(k, len(arr)):
        if minHeap.heap[0][0] < arr[i][0]:
            minHeap.heap[0] = arr[i]
            minHeap.siftDown(0, len(minHeap.heap), minHeap.heap)
    return [v for i,v in minHeap.heap]

Initialize: O(klog(k))
SiftDown: O(log(k))
Assume there are n distinct elements in the array
Total time:  O(nlog(k))
Space: O(k)