题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
Solution
使用快排解决,基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组的左边,比第k个数字大的所有数字都位于数组的右边。调整之后,位于数组左边的k个数字就是最小的k个数字(这k个数字不一定是排序的)。O(N)
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def quick_sort(lst):
if not lst:
return []
pivot = lst[0]
left = quick_sort([x for x in lst[1: ] if x < pivot])
right = quick_sort([x for x in lst[1: ] if x >= pivot])
return left + [pivot] + right
if tinput == [] or k > len(tinput):
return []
tinput = quick_sort(tinput)
return tinput[: k]
class Solution {
public:
void swap(int &fir,int &sec)
{
int temp = fir;
fir = sec;
sec = temp;
}
int getPartition(vector<int> a, int left, int right)
{
int x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int> result;
if(input.empty() || k>input.size() || k<=0) return result;
int start = 0;
int end = input.size()-1;
int index = getPartition(input,start,end);
while(index != (k-1))
{
if(index > (k-1))
{
end = index - 1;
index = getPartition(input,start,end);
}
else
{
start = index + 1;
index = getPartition(input,start,end);
}
}
for(int i=0;i<k;++i)
{
result.push_back(input[i]);
}
return result;
}
};
网友评论