题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
排序后取前k，这里用堆排序
class Solution
{
public:
vector<
int> GetLeastNumbers_Solution(vector<
int> input,
int k)
{
vector<
int>
res;
if (input.empty() || k >
input.size())
return res;
HeapSort(input);
for (
int i =
0; i < k; i++
)
{
res.push_back(input[i]);
}
return res;
}
void PercDown(vector<
int> &arr,
int N,
int i)
{
int child;
int tempNode;
// 2*i + 1 ： leftChild
for (tempNode = arr[i]; (
2 * i +
1) < N; i =
child)
{
child =
2 * i +
1;
if (child != N -
1 && arr[child +
1] >
arr[child])
child++
;
if (tempNode <
arr[child])
arr[i] =
arr[child];
else
break;
}
arr[i] =
tempNode;
}
void HeapSort(vector<
int> &
arr)
{
int len =
arr.size();
if (len ==
0)
return;
for (
int i = len /
2; i >=
0; i--
)
PercDown(arr, len, i); //biuld
for (
int i = len -
1; i >
0; i--
)
{
swap(arr[0], arr[i]);
//delete
PercDown(arr, i,
0);
}
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10114661.html
