题解 | #NC119-最小的K个数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param input int整型一维数组 
 * @param inputLen int input数组长度
 * @param k int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
/***************************************************************************
* 算法要求时间复杂度为O(nlogn)，因此用快速排序算法从小到大进行排序
* 最小的K个数的数字下标为[0, k-1]，将原数组input[k]设为'\0',*returnSize = k
****************************************************************************/
int partition(int *input, int left, int right)
{
    int i = left+1;
    int j = right;
    int pivot = input[left];
    
    while(1)
    {
        while(i <= j && input[i] <= pivot) i++;
        while(i <= j && input[j] >= pivot) j--;
        if(i >= j)
            break;
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }
    input[left] = input[j];
    input[j] = pivot;
    return j;
}

int *quickSort(int *input, int left, int right)
{
    if(left < right)//注意循环条件
    {
        int mid = partition(input, left, right);
        input = quickSort(input, left, mid-1);
        input = quickSort(input, mid+1, right);
    }
    return input;
}

int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    int left = 0;
    int right = inputLen-1;
    
    quickSort(input, left, right);
    
    
    input[k] = '\0';
    *returnSize = k;
    return input;
}