# 前K个常见元素

## 例子

```nums[] = {1, 1, 1, 2, 2, 3}
k = 2```
`1 2`

```nums[] = {1}
k = 1```
`1`

## 前K个频繁元素的幼稚方法

1. 建立一个 地图 通过遍历给定数组来计算元素和频率。
2. 根据频率的降序对地图的条目进行排序。
3. 排序图的前k个元素有助于得出答案。

nums [] = {1，1，2，3，3，3，4}和k = 2

### 代码

#### 前K个常见元素的Java代码

```import java.util.*;

class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;

// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}

// Sort the map, according to decreasing order of frequency and store in a set
TreeSet<Element> set = new TreeSet<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Element curr = new Element(entry.getKey(), entry.getValue());
}

// First k elements of the sorted map contributes to the answer
int index = 0;
for (Element element : set) {
System.out.print(element.value + " ");
index++;
if (index == k)
break;
}
System.out.println();
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;

printKFrequent(nums, k);

// Example 2
nums = new int[]{1};
k = 1;

printKFrequent(nums, k);
}

// class representing a element and value pair
static class Element {
int value;
int freq;

public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}```

#### 前K个常见元素的C ++代码

```#include <bits/stdc++.h>
using namespace std;

// structure representing a element and value pair
struct Element {
int value;
int freq;

Element(int v, int f) {
value = v;
freq = f;
}
};

// Comparator to sort elements according to decreasing order of frequency
struct ElemetComp {
bool operator()(const Element &e1, const Element & e2) {
return (e2.freq < e1.freq);
}
};

void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}

// Sort the map, according to decreasing order of frequency and store in a set
set<Element, ElemetComp> set;
unordered_map<int, int>:: iterator itr;
for (itr = map.begin(); itr != map.end(); itr++) {
Element curr(itr->first, itr->second);
set.insert(curr);
}

// First k elements of the sorted map contributes to the answer
int index = 0;
for (auto it = set.begin(); it != set.end(); it++) {
cout<<it->value<<" ";
index++;
if (index == k)
break;
}
cout<<endl;
}

int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;

printKFrequent(nums, k, 6);

// Example 2
int nums2 = {1};
k = 1;

printKFrequent(nums, k, 1);

return 0;
}```

### 复杂度分析

#### 时间复杂度

O（N * log（N））， 因为我们使用了地图。 映射插入元素需要N倍的时间。

## 前K个频繁元素的最佳方法

1. 建立一个 地图 通过遍历给定数组来计算元素和频率。
2. 建立一个 最大堆 根据地图上的频率。
3. 删除堆顶部k次，这就是答案。

### 前K个常见元素的代码

#### Java代码

```import java.util.*;

class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;

// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}

// Construct a max heap of element and frequency according to frequency
PriorityQueue<Element> heap = new PriorityQueue<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});

// Build heap
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
}

// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
System.out.print(heap.poll().value + " ");
}
System.out.println();
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;

printKFrequent(nums, k);

// Example 2
nums = new int[]{1};
k = 1;

printKFrequent(nums, k);
}

// class representing a element and value pair
static class Element {
int value;
int freq;

public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}```

#### C ++代码

```#include <bits/stdc++.h>
using namespace std;

// structure representing a element and value pair
struct Element {
int value;
int freq;

Element(int v, int f) {
value = v;
freq = f;
}
};

// Comparator to sort elements according to decreasing order of frequency
struct ElementComp {
bool operator()(const Element &e1, const Element & e2) {
return (e1.freq < e2.freq);
}
};

void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}

// Construct a max heap of element and frequency according to frequency
priority_queue<Element, vector<Element>, ElementComp> heap;
for (auto itr = map.begin(); itr != map.end(); itr++) {
Element element(itr->first, itr->second);
heap.push(element);
}

// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
Element curr = heap.top();
heap.pop();
cout<<curr.value<<" ";
}
cout<<endl;
}

int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;

printKFrequent(nums, k, 6);

// Example 2
int nums2 = {1};
k = 1;

printKFrequent(nums, k, 1);

return 0;
}```

### 复杂度分析

#### 时间复杂度

O（k log N + N），这里N是元素数。 因为在最坏的情况下，输入中存在的所有数字可能都是不同的。
O（log N）因素的出现是由于需要将元素插入最大堆或优先级队列的时间。