题目：
输入n个整数，找出其中最小的k个数。
例子说明：
例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3 、4
解题思路：
解法一：O(n)时间算法，只有可以修改输入数组时可用。
可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k 个数字（这k 个数字不一定是排序的〉。
解法二： O（nlogk）的算法，精剧适合处理海量数据。
先创建一个大小为k的数据容器来存储最小的k个数字，接下来我们每次从输入的n个整数中读入一个数．如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中：如果容器中己有k 数字了，也就是容器己满，此时我们不能再插入新的数字而只能替换已有的数字。找出这己有的k 个数中的最大值，然后1在这次待插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小，则用这个数替换当前已有的最大值：如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。
因此当容器满了之后，我们要做3 件事情： 一是在k个整数中找到最大数： 二是有可能在这个容器中删除最大数： 三是有可能要插入一个新的数字。我们可以使用一个大顶堆在O(logk）时间内实现这三步操作。
代码实现
Partition方法:
/**
排序 数组
@param inputArray 输入数组(原数组)
@param startIndex 起始 索引
@param endIndex 终止 索引
@param k 前 k 个 元素
*/
void qiuckSort(int *inputArray, int startIndex, int endIndex, int k) {
if(inputArray == NULL || startIndex < 0 || k < 0) {
return;
}
int leftIndex = startIndex;
int rightIndex = endIndex;
int compareValue = inputArray[leftIndex];
while (leftIndex < rightIndex) {
// 从后 往前 遍历 找到 比compareValue 小的 数
while (leftIndex < rightIndex && inputArray[rightIndex] > compareValue) {
rightIndex -- ;
}
inputArray[leftIndex] = inputArray[rightIndex];
// 从前向后 遍历 找到 比compareValue 大的数
while (leftIndex < rightIndex && inputArray[leftIndex] < compareValue) {
leftIndex ++;
}
inputArray[rightIndex] = inputArray[leftIndex];
}
inputArray[leftIndex] = compareValue;
// 前半部分 太长
if (leftIndex > k - 1) {
qiuckSort(inputArray, startIndex, leftIndex - 1, k);
}
// 前半部分 太短
else if(leftIndex < k - 1) {
qiuckSort(inputArray, leftIndex + 1, endIndex, k);
}
}
/**
获取 最小 的 前K 个 数
@param inputArray 输入数组(原数组)
@param inputLength 原数组 长度
@param k 最小的前K 个数
*/
void getLeastNumbersOne(int *inputArray, int inputLength, int k) {
if(inputArray == NULL || inputLength == 0) {
return ;
}
if (k == 0) {
return;
}
qiuckSort(inputArray, 0, inputLength - 1, k);
}
大顶堆方法:
#import <Foundation/Foundation.h>
/**
交互 数组 中 的两个 数字
@param numArray 待排序 数组
@param a 数组 下标
@param b 数组 下标
*/
void heapSwap(int *numArray,int a ,int b){
int temp= numArray[a];
numArray[a] = numArray[b];
numArray[b] = temp;
}
/**
调整 堆
@param numArray 待排序 数组
@param nodeOrder 结点 序号
@param arrayLength 数组 长度
*/
void heapAdjust(int *numArray, int nodeOrder, int arrayLength) {
// 先 保存 当前 值
int tmpValue = numArray[nodeOrder];
//从nodeOrder结点的左子结点开始，也就是2i+1处开始 遍历调整 各个非叶子节点
for(int tmpIndex = nodeOrder * 2 + 1; tmpIndex < arrayLength; tmpIndex = tmpIndex * 2 + 1){
if (tmpIndex + 1 < arrayLength && numArray[tmpIndex] < numArray[tmpIndex + 1]) {
tmpIndex ++;
}
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
if (numArray[tmpIndex] > tmpValue) {
numArray[nodeOrder] = numArray[tmpIndex];
nodeOrder = tmpIndex;
}
else {
break;
}
}
numArray[nodeOrder] = tmpValue;
}
/**
构建 堆
@param numArray 待排序 数组
@param arrayLength 数组 长度
*/
void buildHeap(int *numArray, int arrayLength) {
if(numArray == NULL) {
return;
}
if (arrayLength == 0) {
return;
}
// 非叶子节点最大序号值为arrayLength/2
for (int tmpIndex = arrayLength/2 - 1; tmpIndex >= 0; tmpIndex--) {
heapAdjust(numArray, tmpIndex, arrayLength);
}
}
/**
堆排序
@param numArray 待排序 数组
@param arrayLength 数组 长度
*/
void heapSort (int *numArray, int arrayLength) {
if(numArray == NULL) {
return;
}
if (arrayLength == 0 ||
arrayLength == 1) {
return;
}
// 构建 大顶堆
buildHeap(numArray, arrayLength);
// 倒序 交互 最大数
for(int tmpIndex = arrayLength - 1; tmpIndex > 0; tmpIndex--) {
heapSwap(numArray, 0, tmpIndex);
heapAdjust(numArray, 0, tmpIndex);
}
}
/**
获取 最小 的 前K 个 数
@param inputArray 输入数组(原数组)
@param inputLength 原数组 长度
@param outputArray 输出 数组
@param outputLenghth 输出 数组 长度
*/
void getLeastNumberTwo(int *inputArray, int inputLength, int *outputArray, int outputLenghth) {
if(inputArray == NULL || inputLength == 0) {
return ;
}
if (outputArray == NULL || outputLenghth == 0) {
return;
}
// 遍历 字符串
for (int tmpIndex = 0; tmpIndex < inputLength; tmpIndex++) {
// 小于 输出 数组 长度
if (tmpIndex < outputLenghth) {
outputArray[tmpIndex] = inputArray[tmpIndex];
// 当 输出 数组 满时
if (tmpIndex == (outputLenghth - 1)) {
// 构建 堆
buildHeap(outputArray, outputLenghth);
}
}
// 大于 输出 数组 长度
else {
// 小于 数组 最大值
if(inputArray[tmpIndex] < outputArray[0]) {
outputArray[0] = inputArray[tmpIndex];
heapAdjust(outputArray, 0, outputLenghth);
}
}
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int a[7] = {0, 16, 20, 3, 11, 17, 8};
int b[6] = {0};
getLeastNumberTwo(a, 7, b, 6);
for(int tmpIndex = 0 ;tmpIndex < 6; tmpIndex++) {
printf("%d ", b[tmpIndex]);
}
}
return 0;
}
网友评论