스트림 문제에서 상위 k (또는 가장 빈번한) 숫자 찾기에서 정수를 제공했습니다. 정렬 일부 숫자로 구성됩니다. 문제 설명은 배열에서 요소를 가져와야하며 상단에는 최대 k 개의 숫자 만 가질 수 있습니다. 빈도에 따라 점차적으로 정렬되는 상위 k 개 요소를 인쇄해야합니다.
차례
예
입력
[3, 1, 4, 6, 1] k = 4
산출
3, 1, 3, 1, 3, 4, 1, 3, 4, 6, 1, 3, 4, 6
스트림의 상위 k (또는 가장 빈번한) 숫자에 대한 설명
- 우리가 1을 읽을 때st 배열의 요소가 3이고 지금까지 주파수가 1 인 유일한 요소로 '3'을 인쇄합니다.
- 배열의 두 번째 요소 인 2을 읽고 동일한 주파수를 가진 1과 3이 있습니다. 즉, 1이지만 1은 1보다 작으므로 3 1을 인쇄합니다.
- 다음 단계에서 배열의 세 번째 요소 인 3를 읽고 동일한 주파수 즉, 4을 가진 3, 1, 4가 있지만 정렬 된 순서는 1 1 3 여야합니다.
- 배열의 4 번째 요소 인 6을 읽고 동일한 주파수 즉, 3을 가진 1, 4, 6, 1이 있지만 정렬 된 순서는 1 3 4이어야합니다.
- 배열의 5 번째 요소 인 1을 읽고 3, 1, 4, 6이 모두 같은 주파수를 가질 때 즉, 1이지만 1은 주파수가 1보다 크므로 주파수가 더 큰 요소가 먼저 와야합니다. 1 3 4이어야합니다.
입력
[1, 2, 2, 4, 5] k = 4
산출
1, 1, 2, 2, 1, 2, 1, 4, 2, 1, 4, 5
스트림의 상위 k (또는 가장 빈번한) 숫자에 대한 설명
- 우리가 1을 읽을 때st 배열의 요소가 1이고 지금까지 주파수가 1 인 유일한 요소로 '1'을 인쇄합니다.
- 2 인 배열의 두 번째 요소를 읽고 동일한 주파수를 가진 2와 2을 가지고 있습니다. 즉, 1이지만 1은 1보다 작으므로 2 1를 인쇄합니다.
- 다음 단계에서는 배열의 세 번째 요소 인 3를 읽고 2는 주파수보다 더 큰 주파수를 가지므로 더 높은 주파수를 가진 요소가 먼저 오므로 2 2을 인쇄합니다.
- 배열의 4 번째 요소 인 4를 읽고 주파수가 4 인 1와 1이 있으므로 2 1 4를 인쇄합니다.
- 5 인 배열의 5 번째 요소를 읽고 1, 4, 5가 모두 같은 주파수를 가질 때 즉, 1이지만 2는 주파수가 1보다 크므로 주파수가 더 큰 요소가 먼저 와야합니다. 2 1 4 5.
암호알고리즘
- HashMap을 선언하십시오.
- 배열을 선언하십시오.
- 지도에 각 요소의 빈도를 계산하고 저장합니다.
- 요소를 k + 1 위치에 놓습니다.
- 상단 요소를 검색하고 위치를 가져옵니다.
- 얻은 위치에서 0까지 반복합니다.
- 더 높은 주파수의 요소가 i 옆에 저장되어 있으면 바꿉니다.
- 주파수가 같지만 다음 요소가 더 큰 경우 바꿉니다.
- 배열의 모든 반복에 대해 상위 k를 인쇄합니다.
에 대한 설명 스트림에서 상위 k (또는 가장 빈번한) 숫자 찾기
우리는 배열과 그 안에 몇 가지 숫자를 제공했습니다. 여기에서 각 반복마다 스트림에서 상위 k (또는 가장 빈번한) 숫자를 찾아야합니다. 우리는 그것에 대한 몇 가지 조건을 제공했습니다. 먼저해야 할 일은 각 요소와 그 빈도를 세는 것입니다. 그리고 우리는 그 빈도와 함께 그 요소를지도에 저장할 것입니다. 배열이 반복 될 때마다 요소와 빈도를 입력해야합니다.
빈도로 해당 맵에 넣은 첫 번째 요소를 반복 한 다음 해당 배열의 요소를 k 번째 위치의 임시 배열에 복사했다고 가정합니다. 그런 다음 임시 배열에서 해당 요소의 위치를 찾아 임시 변수에 저장하고 해당 임시 변수를 카운트 1만큼 줄입니다.
반복 while 루프 해당 위치 (임시 변수)에서 0으로 설정하고 그 안에 세 가지 조건을 설정합니다. 해당 위치 값의 빈도가 다음 요소의 빈도보다 작 으면 두 요소를 모두 바꿉니다. 빈도가 비슷하지만 다음 요소가 그에 따라 교체하는 것보다 큰 경우. 그렇지 않으면 루프를 끊어야합니다.
기본 아이디어는 모든 상위 k 요소 쌍을 감소하지 않는 순서로 정렬해야한다는 것입니다. 그러나 해당 상위 k 요소 쌍의 요소 중 어떤 요소가 다른 요소의 주파수보다 더 큰 주파수를 갖는 경우이를 넣어야합니다. 요소를 순서대로 그래서 숫자 2가 주파수 2를 가지고 반복되기 때문에 우리 순서에서 가장 먼저 나오는 이유입니다. 그래서 그것은 우리 순서에서 가장 큰 주파수 숫자였습니다.
모든 상위 k 요소 쌍을 교환하고 배열 한 후에는 스트림에서 상위 k (또는 가장 빈번한) 숫자를 인쇄해야합니다.
스트림에서 상위 k (또는 가장 빈번한) 숫자 찾기 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void kTop(int arr[], int n, int k)
{
vector<int> topArray(k + 1);
unordered_map<int, int> freq;
for (int l = 0; l < n; l++)
{
freq[arr[l]]++;
topArray[k] = arr[l];
auto itr = find(topArray.begin(), topArray.end() - 1, arr[l]);
for (int i = distance(topArray.begin(), itr) - 1; i >= 0; --i)
{
if (freq[topArray[i]] < freq[topArray[i + 1]])
swap(topArray[i], topArray[i + 1]);
else if ((freq[topArray[i]] == freq[topArray[i + 1]])
&& (topArray[i] > topArray[i + 1]))
swap(topArray[i], topArray[i + 1]);
else
break;
}
for (int i = 0; i < k && topArray[i] != 0; ++i)
cout << topArray[i] << ' ';
}
cout << endl;
}
int main()
{
int k = 4;
int arr[] = { 5, 2, 1, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
kTop(arr, n, k);
return 0;
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5
자바 프로그램
import java.io.*;
import java.util.*;
class topKElements
{
public static int findTop(int[] arr, int ele)
{
for (int i = 0; i < arr.length; i++)
if (arr[i] == ele)
return i;
return -1;
}
public static void printTopElements(int[] a, int n, int k)
{
int[] topArray = new int[k + 1];
HashMap<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < k + 1; i++)
freq.put(i, 0);
for (int l = 0; l < n; l++)
{
if (freq.containsKey(a[l]))
freq.put(a[l], freq.get(a[l]) + 1);
else
freq.put(a[l], 1);
topArray[k] = a[l];
int i = findTop(topArray, a[l]);
i -= 1;
while (i >= 0)
{
if (freq.get(topArray[i]) < freq.get(topArray[i + 1]))
{
int temp = topArray[i];
topArray[i] = topArray[i + 1];
topArray[i + 1] = temp;
}
else if ((freq.get(topArray[i]) == freq.get(topArray[i + 1])) && (topArray[i] > topArray[i + 1]))
{
int temp = topArray[i];
topArray[i] = topArray[i + 1];
topArray[i + 1] = temp;
}
else
{
break;
}
i -= 1;
}
for (int j = 0; j < k && topArray[j] != 0; j++)
{
System.out.print(topArray[j]+" ");
}
}
System.out.println();
}
public static void main(String args[])
{
int k = 4;
int[] arr = { 5, 2, 1, 3, 2 };
int n = arr.length;
printTopElements(arr, n, k);
}
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5
스트림에서 상위 k 개 (또는 가장 빈번한) 숫자 찾기에 대한 복잡성 분석
시간 복잡성
O (n * k) 각 순회에서 크기의 임시 배열이 "케이" 순회 "엔" 순회됩니다.
공간 복잡성
O (N) HashMap에 요소를 저장하면 "엔" 시간.
