검지 offer: 면접 문제 40 최소 k 개
정수 배열 arr 를 입력 하여 가장 작은 k 개 수 를 찾 아 보 세 요.예 를 들 어 4, 5, 1, 6, 2, 7, 3, 8 이라는 8 개의 숫자 를 입력 하면 가장 작은 4 개의 숫자 는 1, 2, 3, 4 이다.예시 1: 입력: arr = [3, 2, 1], k = 2 출력: [1, 2] 또는 [2, 1] 예시 2: 입력: arr = [0, 1, 2, 1], k = 1 출력: [0]
분석 하 다.
이것 은 매우 전형 적 인 문제 로 세 가지 방법 이 있다. 1. 직접 sort 정렬 은 앞의 K 대 2, 쌓 기 정렬 3, 빠 른 배열 사상 이다.
첫 번 째 해법 은 너무 지루 해서 말 하지 않 겠 습 니 다.
2. 쌓 기 정렬
더 미 는 뿌리 노드 가 아이의 결점 보다 크 고 형제 결점 은 크기 관 계 를 구분 하지 않 는 데이터 구조 이다.
#include
using namespace std;
const int MAXN = 10000;
int n;
int heap[MAXN];
inline int& getRef(int root) {
return heap[root-1];
}
void push(int v) {
heap[n++] = v;
int pos = n, nextPos = pos>>1;
while(pos > 1 && getRef(pos) > getRef(nextPos) )
{
swap(getRef(pos), getRef(nextPos));
pos = nextPos, nextPos >>= 1;
}
}
int pop()
{
swap(getRef(1), getRef(n));
int res = heap[--n];
for(int root = 1; ; ) {
int left = root<<1;
int right = root<<1|1;
if(right <= n && getRef(root) < max(getRef(left), getRef(right))) {
if(getRef(left) > getRef(right)) {
swap(getRef(left), getRef(root));
root = left;
} else {
swap(getRef(right), getRef(root));
root = right;
}
} else if (left <= n && getRef(root) < getRef(left)) {
swap(getRef(left), getRef(root));
root = left;
break;
} else {
break;
}
}
return res;
}
vector<int> getLeastNumbers(vector<int>& arr, int k)
{
for(int i=0; i<arr.size(); i++){
push(arr[i]);
if(n>k)
pop();
}
return vector<int>(heap, heap+k);
}
int main()
{
vector<int> arr;
arr.push_back(1);
arr.push_back(2);
arr.push_back(3);
int k = 2;
getLeastNumbers(arr, k);
}
3. 빠 른 배열 사상
class Solution {
public:
vector<int> ans;
int ansCnt;
void quickSort(vector<int>& arr, int left, int right, int k) {
if(left>right) return;
if(ansCnt == k) return ;
int flag = arr[left];
int i = left, j = right;
while(i<j)
{
while(arr[j]>=flag && i<j) j--;
arr[i] = arr[j];
while(arr[i]<=flag && i<j) i++;
arr[j] = arr[i];
}
arr[i] = flag;
if(i<k){
for(int t=left; t<=i; t++){
ans.push_back(arr[t]);
ansCnt++;
}
if(ansCnt == k)
return;
quickSort(arr, i+1, right, k);
}
if(i>=k)
quickSort(arr, left, i-1, k);
}
vector<int> getLeastNumbers(vector<int>& arr, int k)
{
int l = 0;
int r = arr.size()-1;
quickSort(arr, 0, r, k);
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.