검지 offer: 면접 문제 40 최소 k 개

면접 문제 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;
    }
};

좋은 웹페이지 즐겨찾기