程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 劍指OFFER之最小的K個數(九度OJ1371)

劍指OFFER之最小的K個數(九度OJ1371)

編輯:關於C語言

題目描述:

輸入n個整數,找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字,則最小的4個數字是1,2,3,4,。

 

輸入:

每個測試案例包括2行:

第一行為2個整數n,k(1<=n,k<=200000),表示數組的長度。

第二行包含n個整數,表示這n個數,數組中的數的范圍是[0,1000 000 000]。

 

輸出:

對應每個測試案例,輸出最小的k個數,並按從小到大順序打印。

 

樣例輸入:
8 4
4 5 1 6 2 7 3 8

 

樣例輸出:
1 2 3 4

解題思路:

  我們通過快排找到第k個數,然後比他的小的都在左邊,比他大的都在右邊

void getNumber(int n,int m){
    int i;
    int begin = 0;
    int end = n-1;
    int index = patition(begin,end);
    while(index != m-1){
        if(index > m-1){
            end = index -1;
            index = patition(begin,end);
        }else{
            begin = index+1;
            index = patition(begin,end);
        }
    }
}

 

  在進行一次快排,將數組有序的輸出。

void Qsort(int begin,int end){
    if(begin >= end)
        return ;
    else{
        int middle = patition(begin,end);
        Qsort(begin,middle-1);
        Qsort(middle+1,end);
    }
}

  快排的代碼如下:

int patition(int begin,int end){
    int index,small;
    small = begin-1;
    for(index = begin;index < end;index++){
        if(gArr[index] < gArr[end]){
            small++;
            if(small != index)
                swap(index,small);
        }
    }
    small++;
    swap(small,end);
    return small;
}
void swap(int i,int j){
    int tmp = gArr[j];
    gArr[j] = gArr[i];
    gArr[i] = tmp;
}

 

全部代碼:

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200000
int  gArr[MAXSIZE]={0};
void getNumber(int n,int m);
void Qsort(int begin,int end);
int patition(int begin,int end);
void swap(int i,int j);
int main(){
    int n,m,i;
    while(scanf("%d %d",&n,&m)!=EOF && n>=1 && n<=200000){
        for(i=0;i<n;i++)
            scanf("%d",&gArr[i]);
        getNumber(n,m);
        Qsort(0,m-1);
        for(i=0;i<m-1;i++){
            printf("%d ",gArr[i]);
        }
        printf("%d\n",gArr[m-1]);
    }
    return 0;
}
void Qsort(int begin,int end){
    if(begin >= end)
        return ;
    else{
        int middle = patition(begin,end);
        Qsort(begin,middle-1);
        Qsort(middle+1,end);
    }
}
void getNumber(int n,int m){
    int i;
    int begin = 0;
    int end = n-1;
    int index = patition(begin,end);
    while(index != m-1){
        if(index > m-1){
            end = index -1;
            index = patition(begin,end);
        }else{
            begin = index+1;
            index = patition(begin,end);
        }
    }
}
int patition(int begin,int end){
    int index,small;
    small = begin-1;
    for(index = begin;index < end;index++){
        if(gArr[index] < gArr[end]){
            small++;
            if(small != index)
                swap(index,small);
        }
    }
    small++;
    swap(small,end);
    return small;
}
void swap(int i,int j){
    int tmp = gArr[j];
    gArr[j] = gArr[i];
    gArr[i] = tmp;
}
/**************************************************************
    Problem: 1371
    User: xhalo
    Language: C
    Result: Accepted
    Time:950 ms
    Memory:1696 kb
****************************************************************/

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved