leetcode 검 은 offer 면접 문제 40. 최소 k 개 수 를 가리킨다.

leetcode lcof 면접 문제 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]
제한:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

문제 풀이 방향: 최대 더미
이 문 제 는 가장 많은 사상 으로 길이 가 k 인 최대 배열 을 유지 할 수 있 습 니 다. 만약 에 새로운 요소 가 최대 쌓 인 요소 보다 크 면 현재 의 새로운 요 소 를 쌓 인 요소 와 교환 한 다음 에 쌓 인 유지 (즉, 가장 많은 성질 유지) 를 할 수 있 습 니 다. 유지 과정 은 쌓 인 지붕 에서 시작 하여 서브 노드 에 현재 요소 보다 큰 값 이 존재 하면 서브 노드 와 현재 요 소 를 교환 합 니 다.현재 요소 인덱스 값 을 교환 서브 노드 인덱스 로 지정 합 니 다. 잎 노드 를 만 나 거나 현재 요소 보다 큰 하위 노드 가 없 으 면 순환 이 끝 납 니 다.

vector<int> getLeastNumbers(vector<int>& arr, int k) {
     
    //        or k==0  
    if(k==0||arr.empty()) return vector<int>();
    //   
    vector<int> ans(k,INT_MAX);
    for(int x:arr){
     
        //             ，               k 
        if(x<ans[0]){
     
            //    
            ans[0]=x;
            //       
            maintain_heap(ans);
        }

    }
    return ans;
}

//     
void maintain_heap(vector<int>& ans){
     
    int i=0;
    while(i<ans.size()){
     
        //         ,          ，     ，    。
        if((2*i+1)>=ans.size()) break;
        
        int left=ans[2*i+1];
        //max_num        
        int max_num=left;
        //       
        if((2*i+2)<ans.size()){
     
            int right=ans[2*i+2];
            max_num=left>right?left:right;
            //   
            if(ans[i]<max_num){
     
                if(left>right){
     
                    //         
                    swap(ans[i],ans[2*i+1]);
                    i=2*i+1;
                }else{
     
                    swap(ans[i],ans[2*i+2]);
                    i=2*i+2;
                }
            }
            else{
     //    ，       
                break;
            }
        }
        else{
     //      
            if(ans[i]<max_num){
     //      ，  
                swap(ans[i],ans[2*i+1]);
                i=2*i+1;
            }
            else break;//      ，  
        }
        
    }
}

void swap(int& x,int& y){
     
    int t=x;
    x=y;
    y=t;
}

cpp 의 stl 용기 priorityqueue 우선 대기 열 에서 도 최대 수 요 를 빠르게 완성 할 수 있 습 니 다.
알고리즘 시간 복잡 도 O (nlogk), 공간 복잡 도 O (k).