[编程题]最小的K个数

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if tinput == [] or k > len(tinput):
return []
tinput.sort()
return tinput[: k]```

```# -*- 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]```

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[: mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
l, r, res = 0, 0, []
while l < len(left) and r < len(right):
if left[l] <= right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
res += left[l:]
res += right[r:]
return res
if tinput == [] or k > len(tinput):
return []
tinput = merge_sort(tinput)
return tinput[: k]```

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def siftup(lst, temp, begin, end):
if lst == []:
return []
i, j = begin, begin * 2 + 1
while j < end:
if j + 1 < end and lst[j + 1] > lst[j]:
j += 1
elif temp > lst[j]:
break
else:
lst[i] = lst[j]
i, j = j, 2 * j + 1
lst[i] = temp

def heap_sort(lst):
if lst == []:
return []
end = len(lst)
for i in range((end // 2) - 1, -1, -1):
siftup(lst, lst[i], i, end)
for i in range(end - 1, 0, -1):
temp = lst[i]
lst[i] = lst[0]
siftup(lst, temp, 0, i)
return lst

if tinput == [] or k > len(tinput):
return []
tinput = heap_sort(tinput)
return tinput[: k]```

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def bubble_sort(lst):
if lst == []:
return []
for i in range(len(lst)):
for j in range(1, len(lst) - i):
if lst[j-1] > lst[j]:
lst[j-1], lst[j] = lst[j], lst[j-1]
return lst

if tinput == [] or k > len(tinput):
return []
tinput = bubble_sort(tinput)
return tinput[: k]```

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def select_sort(lst):
if lst == []:
return []
for i in range(len(lst)-1):
smallest = i
for j in range(i, len(lst)):
if lst[j] < lst[smallest]:
smallest = j
lst[i], lst[smallest] = lst[smallest], lst[i]

return lst

if tinput == [] or k > len(tinput):
return []
tinput = select_sort(tinput)
return tinput[: k]```

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def Insert_sort(lst):
if lst == []:
return []
for i in range(1, len(lst)):
temp = lst[i]
j = i
while j > 0 and temp < lst[j - 1]:
lst[j] = lst[j - 1]
j -= 1
lst[j] = temp
return lst

if tinput == [] or k > len(tinput):
return []
tinput = Insert_sort(tinput)
return tinput[: k]```

```import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
int length = input.length;
if(k > length || k == 0){
return result;
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < length; i++) {
if (maxHeap.size() != k) {
maxHeap.offer(input[i]);
} else if (maxHeap.peek() > input[i]) {
Integer temp = maxHeap.poll();
temp = null;
maxHeap.offer(input[i]);
}
}
for (Integer integer : maxHeap) {
}
return result;
}
}```

1、全排序  时间复杂度O（nlogn）  *通过牛客*

```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.empty()||k>input.size()) return res;

sort(input.begin(),input.end());

for(int i=0;i<k;i++)
res.push_back(input[i]);

return res;

}
};```
2、Partiton思想 时间复杂度O(n)   *通过VS2013，牛客超时，很纳闷，欢迎找错*

```class Solution {
public:
int Partition(vector<int>& input, int begin, int end)
{
int low=begin;
int high=end;

int pivot=input[low];
while(low<high)
{
while(low<high&&pivot<=input[high])
high--;
input[low]=input[high];
while(low<high&&pivot>=input[low])
low++;
input[high]=input[low];
}
input[low]=pivot;
return low;
}

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

int len=input.size();
if(len==0||k>len) return vector<int>();
if(len==k) return input;

int start=0;
int end=len-1;
int index=Partition(input,start,end);
while(index!=(k-1))
{
if(index>k-1)
{
end=index-1;
index=Partition(input,start,end);
}
else
{
start=index+1;
index=Partition(input,start,end);
}
}

vector<int> res(input.begin(), input.begin() + k);

return res;
}

};```
3、最大堆 时间复杂度O（nlogk）  *通过VS2013，牛客超时，很纳闷，欢迎找错*
```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int len=input.size();
if(len<=0||k>len) return vector<int>();

vector<int> res(input.begin(),input.begin()+k);
//建堆
make_heap(res.begin(),res.end());

for(int i=k;i<len;i++)
{
if(input[i]<res[0])
{
//先pop,然后在容器中删除
pop_heap(res.begin(),res.end());
res.pop_back();
//先在容器中加入，再push
res.push_back(input[i]);
push_heap(res.begin(),res.end());
}
}
//使其从小到大输出
sort_heap(res.begin(),res.end());

return res;

}
};```
4、红黑树：multiset集合  利用仿函数改变排序顺序 时间复杂度O（nlogk）  *通过牛客*
```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int len=input.size();
if(len<=0||k>len) return vector<int>();

//仿函数中的greater<T>模板，从大到小排序
multiset<int, greater<int> > leastNums;
vector<int>::iterator vec_it=input.begin();
for(;vec_it!=input.end();vec_it++)
{
//将前k个元素插入集合
if(leastNums.size()<k)
leastNums.insert(*vec_it);
else
{
//第一个元素是最大值
multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
//如果后续元素<第一个元素，删除第一个，加入当前元素
if(*vec_it<*(leastNums.begin()))
{
leastNums.erase(greatest_it);
leastNums.insert(*vec_it);
}
}
}

return vector<int>(leastNums.begin(),leastNums.end());
}
};```

java实现。

```public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> al = new ArrayList<Integer>();
if (k > input.length) {
return al;
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < input.length - i - 1; j++) {
if (input[j] < input[j + 1]) {
int temp = input[j];
input[j] = input[j + 1];
input[j + 1] = temp;
}
}
}
return al;
}```

```class Solution {
public:
void swap(int &fir,int &sec)
{
int temp = fir;
fir = sec;
sec = temp;
}

int getPartition(vector<int> &input,int start,int end)
{
if(input.empty() || start>end) return -1;
int temp = input[end];
int j = start - 1;
for(int i=start;i<end;++i)
{
if(input[i]<=temp)
{
++j;
if(i!=j) swap(input[i],input[j]);
}
}
swap(input[j+1],input[end]);
return (j+1);
}

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;
}
};```

(1) 遍历输入数组，将前k个数插入到推中；（利用multiset来做为堆的实现）
(2) 继续从输入数组中读入元素做为待插入整数，并将它与堆中最大值比较：如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还大，则抛弃这个数，继续读下一个数。

```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int> result;
int len = input.size();
if(input.empty() || k<=0 || len < k) return result;

multiset<int, greater<int> > leastNumbers; // 从大到小排序
multiset<int, greater<int> >::iterator iterGreater; // 定义迭代器

vector<int>::iterator iter = input.begin();
for(; iter != input.end(); ++iter)
{
// 将前k个数直接插入进multiset中，注意是小于K
if(leastNumbers.size() < k)
{
leastNumbers.insert(*iter);
}
else
{
// 因为设置的从大到小排序，故multiset中第一个位置的元素即为最大值
iterGreater = leastNumbers.begin();

// 如果input中当前元素比multiset中最大元素小，则替换；即保持multiset中这k个元素是最小的。
if(*iter < *(leastNumbers.begin()))
{
// 替换掉当前最大值
leastNumbers.erase(iterGreater);
leastNumbers.insert(*iter);
}
}
}

for(iterGreater = leastNumbers.begin();iterGreater!=leastNumbers.end();++iterGreater)
{
result.push_back(*iterGreater); // 将multiset中这k个元素输出
}

return result;
}
};```

```/*
*基于堆排序算法，构建最大堆。时间复杂度为O(nlogk)
*如果用快速排序，时间复杂度为O(nlogn)；
*如果用冒泡排序，时间复杂度为O(n*k)
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list=new ArrayList<Integer>();
//检查输入的特殊情况
if(input==null || input.length<=0 || input.length<k){
return list;
}
//构建最大堆
for(int len=k/2-1; len>=0; len--){
}
//从第k个元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆。
//最终堆里的就是最小的K个数。
int tmp;
for(int i=k; i<input.length; i++){
if(input[i]<input[0]){
tmp=input[0];
input[0]=input[i];
input[i]=tmp;
}
}
for(int j=0; j<k; j++){
}
return list;
}

public void adjustMaxHeapSort(int[] input, int pos, int length){
int temp;
int child;
for(temp=input[pos]; 2*pos+1<=length; pos=child){
child=2*pos+1;
if(child<length && input[child]<input[child+1]){
child++;
}
if(input[child]>temp){
input[pos]=input[child];
}else{
break;
}
}
input[pos]=temp;
}
}```

## Sorting O(nlogn)

Time complexity is O(nlogn)

```public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return res;
}
Arrays.sort(input);
for (int i = 0; i < k; i++) {
}
return res;
}
}```

## PriorityQueue O(nlogk)

Time complexity is O(nlogk)

```public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return res;
}
Queue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());

for (int i = 0; i < input.length; i++) {

if (queue.size() < k) {
} else {
if (input[i] < queue.peek()) {
queue.remove();
}
}
}
while (!queue.isEmpty()) {
}
return res;
}
}```

```so还是老一套，一定要记住partition函数咋写！！！
import random
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
n = len(tinput)
if n<=0 or k>n:
return []
if k==0:
return []
start = 0
end = n-1
index = self.partition(tinput,start,end)
while index != k-1:
if index >k-1:
end = index - 1
index = self.partition(tinput,start,end)
else:
start = index +1
index = self.partition(tinput,start,end)
res = tinput[:k]
res=sorted(res)
return res

def partition(self,arr,start,end):
if start==end:
p=start
else:
p = random.randrange(start,end)
arr[p],arr[end]=arr[end],arr[p]
small = start-1
for i in range(start,end):
if arr[i]<arr[end]:
small+=1
if small != i:
arr[small],arr[i]=arr[i],arr[small]
small +=1
arr[small],arr[end]=arr[end],arr[small]
return small```

(如果是要取最大值就是用最大堆）

```class Solution {
private:
void heapSort(vector<int> &input, int root, int end){
for(int j = end -1; j >= root; j --){
int parent = (j + root -1)/2;
if(input[parent] > input[j]){
int temp = input[j];
input[j] = input[parent];
input[parent] = temp;
}
}
}

public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result ;
if(k > input.size()) return result;
for(int i = 0; i < k ; i ++){
heapSort(input,i,input.size());
result.push_back(input[i]);
}
return result;
}
};```

```import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
// [4,5,1,6,2,7,3,8],0
if (input == null || k > input.length || k <= 0)    return list;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
public int compare(Integer i1, Integer i2) {
return i2.compareTo(i1);
}
});
int len = input.length;
for (int i = 0; i < len; ++i) {
if (queue.size() != k) {
queue.offer(input[i]);
} else if (queue.peek() > input[i]) {
queue.poll();
queue.offer(input[i]);
}
}
Iterator<Integer> it = queue.iterator();
while (it.hasNext()) {
}
return list;
}
} ```

```import java.util.ArrayList;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
// [4,5,1,6,2,7,3,8],0
if (input == null || k > input.length || k <= 0)
return list;
int[] target = new int[k];
int len = input.length;
for (int i = 0; i < len; ++i) {
if (i < k) {
target[i] = input[i];
heapInsertSiftUp(target, i, target[i]);
} else {
if (target[0] > input[i]) { // 最大堆下沉
target[0] = input[i];
siftDown(target, 0, target[0]);
// 相比优先级队列，这里不会offer操作(里面有上浮)，少了一步上浮调整，效率高了不止一丁点
}
}
}
for (int i = 0; i < k; ++i) {
}
return list;
}

private void heapInsertSiftUp(int[] target, int index, int x) {
while (index > 0) {
int parent = (index - 1) >>> 1;
if (greater(x, target[parent])) {
target[index] = target[parent]; // 往下拉，避免直接上浮覆盖前面的值
index = parent;
} else {
break;
}
}
target[index] = x;
}

private boolean greater(int i, int j) {
return i > j;
}

private void siftDown(int[] target, int k, int x) {
int half = target.length >>> 1;
while (k < half) {
int child = (k << 1) + 1; // 默认先左孩子
int big = target[child];
int right = child + 1;
if (right < target.length && greater(target[right], big)) {
big = target[right];
child = right; // 可以直接一步big = target[child = right];
}
if (greater(x, big)) // x比子节点中的最大值还大，已经是大顶堆了
break; // 往上拉不动了，准备退出把最初堆顶的结点赋值到上一个结点
target[k] = big; // 往上拉
k = child;
}
target[k] = x;
}
}
```

Java版本

```    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> leastNumbers = new ArrayList<Integer>();
while(input==null || k<=0 || k>input.length)
return leastNumbers;
int[] numbers=new int[k];  //用于放最小的k个数
for(int i=0;i<k;i++)
numbers[i]=input[i];//先放入前k个数
for(int i=k/2-1;i>=0;i--){
}
for(int i=k;i<input.length;i++){
if(input[i]<numbers[0]){ //存在更小的数字时
numbers[0]=input[i];
}
}
for(int n:numbers)
return leastNumbers;
}

//最大堆的调整方法，忘记时可以复习一下堆排序。
private void adjustHeap(int[] arr,int start,int end){
int temp=arr[start];
int child=start*2+1;
while(child<=end){
if(child+1<=end && arr[child+1]>arr[child])
child++;
if(arr[child]<temp)
break;
arr[start]=arr[child];
start=child;
child=child*2+1;
}
arr[start]=temp;
}
```

```    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {
ArrayList<Integer> leastNumbers = new ArrayList<Integer>();
while(input==null || k<=0 || k>input.length)
return leastNumbers;
int start=0;
int end=input.length-1;
int index=partition(input,start,end);
while(index!=k-1){
if(index<k-1){
start=index+1;
index=partition(input,start,end);
}else{
end=index-1;
index=partition(input,start,end);
}
}
for(int i=0;i<k;i++){
}
return leastNumbers;
}

private int partition(int[] arr, int start,int end){
int pivotKey=arr[start];
while(start<end){
while(start<end && arr[end]>=pivotKey)
end--;
swap(arr,start,end);
while(start<end && arr[start]<=pivotKey)
start++;
swap(arr,start,end);
}
return start;
}

private void swap(int[] arr, int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
```

```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> Q;
vector<int> res;
if(input.size() < k || k <= 0) return res;
for(int i = 0; i < input.size(); ++i){
if(Q.size() < k) Q.push(input[i]);
else if(input[i] < Q.top()){
Q.pop(); Q.push(input[i]);
}
}
while(!Q.empty()){
res.push_back(Q.top());
Q.pop();
}
return res;

}
};```

```import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;
/*
* 利用TreeSet排序并去除重复元素，利用ArrayList存储并输出
*/
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list=new ArrayList<Integer>();
ArrayList<Integer> list2=new ArrayList<Integer>();
if(input==null||input.length==0||k==0||k>input.length)
return list;
TreeSet<Integer> set=new TreeSet<Integer>();
for(int i=0;i<input.length;i++){
}
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
int x=it.next();
}
for(int i=0;i<k;i++){
}
return list2;
}
}```

```import java.util.ArrayList;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList aList = new ArrayList();
if(input.length == 0 || k > input.length || k <= 0)
return aList;
int low = 0;
int high = input.length-1;
int index = Partition(input,k,low,high);
while(index != k-1){
if (index > k-1) {
high = index-1;
index = Partition(input,k,low,high);
}else{
low = index+1;
index = Partition(input,k,low,high);
}
}
for (int i = 0; i < k; i++)
return aList;
}

int Partition(int[] input,int k,int low,int high){
int pivotkey = input[k-1];
swap(input,k-1,low);
while(low < high){
while(low < high && input[high] >= pivotkey)
high--;
swap(input,low,high);
while(low < high && input[low] <= pivotkey)
low++;
swap(input,low,high);
}
return low;
}

private void swap(int[] input, int low, int high) {
int temp = input[high];
input[high] = input[low];
input[low] = temp;
}
}
```

## 我的答案

```import java.util.ArrayList;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
if(k > input.length || k == 0){
return res;
}
//快排
quick_sort(input,0,input.length-1);
for(int i=0;i<k;i++){
}
return res;
}
//只要low<high就满足递归条件
private void quick_sort(int[] arr,int low,int high){
if(low < high){
//三色国旗，每次partion之后实现将小于基准数和大于基准数的值想办法搞到两边去
//返回的数组是一个长度为2的数组，分别放等于基准数的起始坐标和终止坐标
int[] p = partion(arr,low,high);
//对小于基准数的地方再次递归来搞成三色国旗
quick_sort(arr,low,p[0]-1);
//对大于基准数的地方也再次递归搞成三色国旗
quick_sort(arr,p[1]+1,high);
}
}
//三色国旗，尤其注意的是下标
private int[] partion(int[] arr,int low,int high){
int less = low - 1;
int more = high + 1;
int curr = low;
int num = arr[curr];
while(curr < more){
//小于基准值则跟++less交换，大于基准值则跟--more交换，相等则不管，继续前进
if(arr[curr] < num){
swap(arr,++less,curr++);
}else if(arr[curr] > num){
swap(arr,curr,--more);
}else{
curr++;
}
}
return new int[]{less,more};
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}```

```import java.util.ArrayList;
public class Solution {
ArrayList res = new ArrayList();
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
//由于是找前k个数字，是比较小的，所以适合用小跟堆来解决
//因为大根堆先得到的是最大值，时间复杂度无法达到理想的nlogk
//整个过程是对数组进行操作的，但是与操作一颗二叉树是一样的，因为二叉堆是可以用数组来表示的
//数组的第一个元素就是二叉堆的root
//我们要保证是最小堆，那么每次从root拿到的数必然是最小的数
//root提取出来之后，将root和最后一个数交换后需要重新调整堆维持堆的性质
if(k == 0 || k > input.length){
return res;
}
heapSort(input,k);
return res;
}
private void heapSort(int[] arr,int k){
if(arr == null || arr.length < 2){
return;
}
//初步构建起一个最小堆，此时root是最小的一个数
for(int i=0;i<arr.length;i++){
heapInsert(arr,i);
}
int heapSize = arr.length;
swap(arr,0,--heapSize);
//将最小的数此时也放进list中，如果k恰好为1那么直接返回
if(res.size() == k){
return;
}
while(heapSize > 0){
//在对[0,heapSize]间构建最小堆，每一轮都找到最小值，然后交换到最后
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
//每次都将堆中最小的数拿到heapSize索引处，所以直接添加进结果集中，结果集大小为k了则立即结束
if(res.size() == k){
return;
}
}
}
//初步构建最小堆，即构建完毕之后root为堆中最小值
private void heapInsert(int[] arr,int i){
while(arr[i] < arr[(i-1)/2]){
//如果比它的父亲小则与父亲交换
swap(arr,i,(i-1)/2);
i = (i-1)/2;
}
}
//上浮过程，每次将root和最后一个数字进行交换，然后重新构建最小堆
private void heapify(int[] arr,int index,int heapSize){
int left = index * 2 + 1;
while(left < heapSize){
//如果右子节点也没有越界的话，则从左右中挑出一个最小值
int least = left+1 < heapSize && arr[left+1]<arr[left] ? left+1 : left;
//再与当前结点做比较
int minIndex = arr[index] < least ? index : least;
//最小的就是index的话，则不用再比较了，已经是最小值了
if(minIndex == index){
break;
}
//不是的话，则要进行交换
swap(arr,index,least);
index = minIndex;
left = index * 2 + 1;
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}```

```//堆排序，复杂度是o(nlogn)，比较稳定适合大数据量的排序，如果是快排的话分的不均匀容易引起
//复杂度是o（n^2）,快排的话大数据量容易引起OOM
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(input==null||input.length==0||input.length<k){
return result;
}
//构建大顶堆
for(int i=k/2-1;i>=0;i--){
}
//我们前k个元素的大顶堆已经构建好了，剩下的就是其余的和大顶堆的最大值比较了
for(int i=k;i<input.length;i++){
if(input[i]<input[0]){
int temp=input[i];
input[i]=input[0];
input[0]=temp;

}
}
//我们将调整好的前k个数放进链表里面
for(int i=0;i<k;i++){
}
return result;

}

//构建大顶堆
public  void adjustHeap(int[] input,int i,int k){
//先把最上面根节点保存了
int temp=input[i];
for(int j=i*2+1;j<=k;j=j*2+1){
//j可以等于k，但是下面的程序不能，我们还要判断j和j+1呢
if(j<k&&input[j]<input[j+1]){
j++;
}
if(temp>input[j]){
break;
}
input[i]=input[j];
i=j;
}
input[i]=temp;
}
}```

```class Solution {
public:
int partion(vector<int>& input, int beg, int end)
{
int key = input[beg];
while (beg < end)
{
while (beg < end && input[end] >= key)end--;
input[beg] = input[end];
while (beg < end && input[beg] <= key)beg++;
input[end] = input[beg];
}
input[beg] = key;
return beg;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if (input.size() == 0 || input.size() < k || k <= 0)
return {};
int pos = partion(input, 0, input.size() - 1);
while (pos != k - 1)
{
if (pos > k - 1)
pos = partion(input, 0, pos - 1);
else
pos = partion(input, pos + 1, input.size() - 1);
}
vector<int> res(input.begin(), input.begin() + k);
return res;
}
};```

```#Pythonban
#利用堆排序 最小堆
# -*- coding:utf-8 -*-
class Solution:

def minFixHeap(self,t,i,n):
tmp = t[i]
j = i*2+1
while j < n:
if j+1 <n and t[j+1] < t[j]:
j+=1
if t[j] >= tmp:
break
t[i] = t[j]
i = j
j = i*2 +1
t[i] = tmp

def GetLeastNumbers_Solution(self, tinput, k):
lens = len(tinput)
if k>lens or k <0 or lens ==0:
return []

for i in range(lens/2,-1,-1):
self.minFixHeap(tinput,i,lens)

res = []
for i in range(lens-1,lens-k-1,-1):
res.append(tinput[0])
tinput[0] = tinput[i]
self.minFixHeap(tinput,0,i)
return res

t = [3,2,4,1,5]
print Solution().GetLeastNumbers_Solution(t,3)```

```import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
// 尼玛，真是奇葩，竟然返回一个空的list链表。。。。出题的太不负责任了
if (input.length < k || k == 0) {
return list;
}

for (int i = 0; i < input.length; i++) {
if (list.size() < k || (list.size() >= k && list.get(k - 1) > input[i])) {
int j;
// 判断list的长度是否已经大于了k，这是为了确定下面for循环的起始位置
int startIndex = list.size() > k? k-1:list.size() - 1;
for (j = startIndex; j > -1 && list.get(j) > input[i]; j--);
}

}
// 将多于k的部分去除掉
while (list.size() > k) {
list.remove(k);
}

return list;
}
}```

```import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
Arrays.sort(input);//快速排序
ArrayList<Integer> list=new ArrayList<Integer>();
if(k>input.length|k<=0){//判断是否存在越界
return list;
}else{for (int i = 0; i < k; i++) {
}
return list;
}
}
}```

1291条回答 113629浏览

# 通过挑战的用户

• 2019-10-16 23:25:40
• 2019-10-16 23:07:17
• 2019-10-16 23:01:33
• 2019-10-16 23:01:07
• 2019-10-16 22:45:46

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题