leetcode * 347. 앞의 K 개 고주파 요소 (쌓 기 정렬)
48692 단어 Leetcode#쌓다최소 / 최대 k 개수leetcode
검 지 Offer 40. 최소 k 개 수 * 215. 배열 의 K 번 째 최대 원소 * 347. 앞의 K 개 고주파 원소
빈 정수 그룹 을 지정 하고 주파수 가 나 오기 전에 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 개의 고주파 요소 의 집합 이 유일 하 다 는 것 입 니 다.너 는 임의의 순서에 따라 답안 을 되 돌려 줄 수 있다.
[문제 풀이 사고 1] map, 작은 지붕 더미
맵 으로 각 요소 가 나타 나 는 횟수 를 기록 하고 정렬 한 후 주파수 가 가장 높 은 k 개 수 를 얻 습 니 다.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int temp : nums) {
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
int len = map.size();
int[][] order = new int[len][2];
int index = 0;
for(int temp : map.keySet()) {
order[index][0] = temp;
order[index][1] = map.get(temp);
index++;
}
Arrays.sort(order, (a, b) -> b[1] - a[1]);
int[] ans = new int[k];
for(int i = 0; i < k; i++) {
ans[i] = order[i][0];
}
return ans;
}
}
가장 쉬 운 방법 은 '출현 횟수 배열' 에 정렬 하 는 것 이다.그러나 O (N) 개의 서로 다른 출현 횟수 가 있 을 수 있 기 때문에 전체적인 알고리즘 복잡 도 는 O (NLogN) 에 달 하고 제목 의 요 구 를 만족 시 키 지 못 한다.쌓 인 사상 개선 을 이용 할 수 있 습 니 다. k 크기 의 작은 지붕 을 유지 한 다음 에 '출현 횟수 배열' 을 옮 겨 다 닐 수 있 습 니 다.
옮 겨 다 니 기 가 완 료 된 후에 쌓 인 요 소 는 '출현 횟수 배열' 의 앞 k 큰 값 을 대표 합 니 다.다음은 우선 대기 열 이라는 기 존 유형 을 사용 하여 이 루어 졌 으 며, 작은 지붕 더 미 를 수 동 으로 실현 할 수 있 습 니 다.
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;
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums){
map.put(n, map.getOrDefault(n, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
queue.addAll(map.entrySet());
int[] ans = new int[k];
for (int i = 0; i < k && !queue.isEmpty(); ++i){
ans[i] = queue.poll().getKey();
}
return ans;
}
}
수 동 으로 쌓 기
class Solution {
//
Map<Integer , Integer> map = new HashMap<>();
public int[] topKFrequent(int[] nums, int k) {
int[] heap = new int[k];
for(int i : nums){
map.put(i , map.getOrDefault(i,0) + 1);
}
Iterator it = map.keySet().iterator();
int i = 0;
while(it.hasNext()){
// k ， k ，
if( i < k){
heap[i] = (Integer)it.next();
i++;
if(i == k){
for(int j = k/2 -1 ; j >= 0 ; j--){
heapSort(heap,j);
}
}
}else{
// ， ， ， ，
int key = (Integer)it.next();
if(map.get(key) > map.get(heap[0])) heap[0] = key;
heapSort(heap , 0);
}
}
return heap;
}
//
// ， ， map value
public void heapSort(int[] heap , int i){
int temp = heap[i];
for(int j = 2*i + 1 ; j < heap.length ; j = 2*j + 1){
if(j+1 < heap.length && map.get(heap[j+1]) < map.get(heap[j])) j++;
if(map.get(heap[j]) < map.get(temp)){
heap[i] = heap[j];
i = j;
}else break;
}
heap[i] = temp;
}
}
[문제 풀이 사고 2] 빨리 배열 (연구 대기)
배열 arr [l... r] 를 빠르게 정렬 하 는 과정 에서 먼저 배열 을 두 부분 arr [i... q - 1] 과 arr [q + 1... j] 로 나 누고 arr [i... q - 1] 의 모든 값 이 arr [q] 를 초과 하지 않 으 며 arr [q + 1.. j] 의 모든 값 이 arr [q] 보다 크다.k 와 왼쪽 하위 배열 arr [i... q - 1] 의 길이 (q - i) 의 크기 관계 에 따라:
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);
}
List<int[]> values = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{
num, count});
}
int[] ret = new int[k];
qsort(values, 0, values.size() - 1, ret, 0, k);
return ret;
}
public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
int picked = (int) (Math.random() * (end - start + 1)) + start;
Collections.swap(values, picked, start);
int pivot = values.get(start)[1];
int index = start;
for (int i = start + 1; i <= end; i++) {
if (values.get(i)[1] >= pivot) {
Collections.swap(values, index + 1, i);
index++;
}
}
Collections.swap(values, start, index);
if (k <= index - start) {
qsort(values, start, index - 1, ret, retIndex, k);
} else {
for (int i = start; i <= index; i++) {
ret[retIndex++] = values.get(i)[0];
}
if (k > index - start + 1) {
qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
