FilesExpand file tree

 master

/

TopKFrequentElements.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

84 lines (78 loc) · 2.65 KB

 master

/

TopKFrequentElements.java

Copy path

Top

File metadata and controls

• Code
• Blame

84 lines (78 loc) · 2.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

import java.util.*;

public class TopKFrequentElements {

/**

* 首选方法，时间复杂度O(n)，省去了排序

* 结尾注意list的size大于k了，要截一部分

*/

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

int max = 0;

for (int n : nums) {

int count = map.getOrDefault(n, 0) + 1;

map.put(n, count);

max = Math.max(max, count);

}

List<Integer>[] lists = new LinkedList[max + 1];

for (int key : map.keySet()) {

int count = map.get(key);

if (lists[count] == null) {

lists[count] = new LinkedList<Integer>();

}

lists[count].add(key);

}

List<Integer> result = new LinkedList<Integer>();

for (int i = lists.length - 1; i >= 0 && result.size() < k; i--) {

if (lists[i] != null) {

result.addAll(lists[i]);

}

}

return result.subList(0, k);

}

/**

* 先统计每个元素次数，再用Priority排序

*/

// 耗时46ms，最差复杂度O(nlgk)，当k<<n时为O(n)

public List<Integer> topKFrequent2(int[] nums, int k) {

HashMap<Integer, Integer> map = new HashMap<>();

for (int n : nums) {

map.put(n, map.getOrDefault(n, 0) + 1);

}

Queue<Integer> queue = new PriorityQueue<Integer>(8, new Comparator<Integer>() {

@Override

public int compare(Integer o1, Integer o2) {

return map.get(o1) - map.get(o2);

}

});

for (Integer n : map.keySet()) {

queue.offer(n);

if (queue.size() > k) {

queue.poll();

}

}

List<Integer> list = new LinkedList<>();

while (!queue.isEmpty()) {

list.add(queue.poll());

}

return list;

}

public List<Integer> topKFrequent3(int[] nums, int k) {

Map<Integer, Integer> map = new HashMap<>();

for(int n: nums){

map.put(n, map.getOrDefault(n,0)+1);

}

TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();

for(int num : map.keySet()){

int freq = map.get(num);

if(!freqMap.containsKey(freq)){

freqMap.put(freq, new LinkedList<>());

}

freqMap.get(freq).add(num);

}

List<Integer> res = new ArrayList<>();

while(res.size()<k){

Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();

res.addAll(entry.getValue());

}

return res;

}

}