347. Top K Frequent Elements（找出数组中出现次数最多的前k个元素）

心已赠人 2022-07-15 12:11 195阅读 0赞

Given a non-empty array of integers, return the k most frequent elements.

For example,  
Given `[1,1,1,2,2,3]` and k = 2, return `[1,2]`.

Note:

*  You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
 *  Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

题目大意：在一个整型数组中，按出现次数从多到少找出前k个元素，将其对应的值存入一个list中返回。

解题思路：

解法一：根据元素出现的次数进行堆排序。

代码如下：（34ms，beats 53.21%）

public List<Integer> topKFrequent(int[] nums, int k) {
    		List<Integer> res = new LinkedList<Integer>();
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int num : nums) {
    			if (map.get(num) == null)
    				map.put(num, 1);
    			else
    				map.put(num, (int) (map.get(num)) + 1);
    		}
    		int len = map.size();
    		Entry<Integer, Integer>[] entrys = new Entry[len + 1];
    		Iterator<Entry<Integer, Integer>> it = map.entrySet().iterator();
    		for (int i = 1; i <= len; i++)
    			entrys[i] = (Entry<Integer, Integer>) it.next();
    
    		for (int i = len / 2; i >= 1; i--) {
    			adjust(entrys, len, i);
    		}
    		for (int i = 1; i <= k; i++) {
    			res.add((Integer) entrys[1].getKey());
    			entrys[1] = entrys[len];
    			len--;
    			adjust(entrys, len, 1);
    		}
    		return res;
    	}
    
    	public void adjust(Entry<Integer, Integer>[] entrys, int len, int i) {
    		int k;
    		entrys[0] = entrys[i];
    		for (k = i * 2; k <= len; k *= 2) {
    			if (k + 1 <= len && entrys[k].getValue() < entrys[k + 1].getValue())
    				k = k + 1;
    			if (entrys[0].getValue() < entrys[k].getValue()) {
    				entrys[i] = entrys[k];
    				i = k;
    			} else
    				break;
    		}
    		entrys[i] = entrys[0];
    	}

解法二：桶排序。

代码如下：（30ms，beats 72.58%）

public List<Integer> topKFrequent2(int[] nums, int k) {
    		List<Integer> res = new LinkedList<Integer>();
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int num : nums) {
    			if (map.get(num) == null)
    				map.put(num, 1);
    			else
    				map.put(num, (int) (map.get(num)) + 1);
    		}
    		int len = nums.length;
    		ArrayList<Integer>[] times = new ArrayList[len + 1];
    		Set<Integer> set = map.keySet();
    		Iterator<Integer> it = set.iterator();
    		while (it.hasNext()) {
    			int num = it.next();
    			int time = map.get(num);
    			if (times[time] == null)
    				times[time] = new ArrayList<>();
    			times[map.get(num)].add(num);
    		}
    		for (int i = len; i >= 0; i--)
    			if (times[i] != null) {
    				it = times[i].iterator();
    				while (k > 0 && it.hasNext()) {
    					res.add(it.next());
    					k--;
    				}
    			}
    		return res;
    	}

解法三：利用Collections.sort函数

代码如下：（36ms，beats 43.93%）

public <T> List<Integer> topKFrequent3(int[] nums, int k) {
    			List<Integer> res = new LinkedList<Integer>();
    			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    			for (int num : nums) {
    				if (map.get(num) == null)
    					map.put(num, 1);
    				else
    					map.put(num, (int) (map.get(num)) + 1);
    			}
    			List<Entry<Integer,Integer>> list = new ArrayList<Entry<Integer,Integer>>(map.entrySet());
    			Collections.sort(list, new Comparator<Entry<Integer,Integer>>() {
    
    				@Override
    				public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
    					return o2.getValue()-o1.getValue();
    				}
    				
    			});
    			for(int i=0;i<k;i++)
    				res.add(list.get(i).getKey());
    			return res;
    		}