首页 > 试题广场 > 最小的K个数
[编程题]最小的K个数
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
用最大堆保存这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) {
            result.add(integer);
        }
        return result;
    }
}

发表于 2016-08-12 10:55:00 回复(51)
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()); 
    }
};

编辑于 2016-07-28 09:54:57 回复(76)
方法一:蒂姆排序
# -*- 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]

发表于 2017-07-24 11:50:16 回复(21)
/*
*基于堆排序算法,构建最大堆。时间复杂度为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--){
            adjustMaxHeapSort(input,len,k-1);
        }
        //从第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;
                adjustMaxHeapSort(input,0,k-1);
            }
        }
        for(int j=0; j<k; j++){
            list.add(input[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;
    }
}

发表于 2016-07-27 22:12:55 回复(21)
java实现。
冒泡排序的思想,只不过最外层循环K次就可以了,也就是说不用全部排序,只挑出符合提议的K个就可以。
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;
				}
			}
			al.add(input[input.length - i - 1]);
		}
		return al;
    }

发表于 2015-10-05 17:15:42 回复(26)
思路一:利用快速排序中的获取分割(中轴)点位置函数getPartitiion
基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组的左边,比第k个数字大的所有数字都位于数组的右边。调整之后,位于数组左边的k个数字就是最小的k个数字(这k个数字不一定是排序的)。O(N)
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;
    }
};
这种思路虽时间复杂度不错,但会修改输入数组,且一般也不易想到。更容易想到的是利用堆排序。
思路二:利用堆排序,O(N logK),适合处理海量数据
(1) 遍历输入数组,将前k个数插入到推中;(利用multiset来做为堆的实现)
(2) 继续从输入数组中读入元素做为待插入整数,并将它与堆中最大值比较:如果待插入的值比当前已有的最大值小,则用这个数替换当前已有的最大值;如果待插入的值比当前已有的最大值还大,则抛弃这个数,继续读下一个数。
这样动态维护堆中这k个数,以保证它只储存输入数组中的前k个最小的数,最后输出堆即可。
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;
    }
};

发表于 2016-08-23 20:13:01 回复(10)

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++) {
            res.add(input[i]);
        }
        return res;
    }
}

PriorityQueue O(nlogk) 

使用PriorityQueue当作Heap,每次返回最大的值。
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) {
                queue.add(input[i]);
            } else {
                if (input[i] < queue.peek()) {
                    queue.remove();
                    queue.add(input[i]);
                }
            }
        }
        while (!queue.isEmpty()) {
            res.add(queue.remove());
        }
        return res;
    }
}
编辑于 2017-08-02 20:30:25 回复(5)
使用简单粗暴的全部排序的方法并不能取得很好的性能,因为只要求k个数,所以使用最小堆就可以了。
(如果是要取最大值就是用最大堆)

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

发表于 2015-09-04 20:31:20 回复(25)
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

发表于 2017-08-27 22:04:09 回复(0)
第一种方法,用优先级队列构造出最大堆,然后不断更新最大堆,每次只和堆顶比,如果比堆顶小,删除堆顶,新数入堆。但是这里利用集合并不好,手写最大堆会比这个更优,因为在超过k个数的时候,优先级队列需要poll和offer操作,poll会下沉恢复堆有序(从堆顶往下一个个比较,相当于把堆顶往下沉,然后到合适位置,堆顶下沉只会赋值一次,并不是下沉的时候比较交换),offer会上升恢复堆有序(从堆底往上一个个比较,相当于把堆底往上浮,堆底上浮只会赋值一次到合适位置,并不是上浮的时候比较交换),而如果手写堆实现的话,仅仅只需要将堆顶元素替换再下沉,就没有了上升恢复堆有序的环节。如果是100W个数找最小的5个数,假如情况比较糟糕,每次都需要更新最大堆堆顶,如果那么使用PriorityQueue将要多做999995(99W近100W)次上升恢复堆有序的操作。可以看一下PriorityQueue的源码就知道。
并且最后迭代的时候要么foreach要么iterator,本质就是iterator迭代。为什么不用for循环去list.add(queue.poll())?虽然也可以出结果,但是queue的poll方法会有下沉恢复堆有序操作,而iterator不会,仅仅是遍历数组。最后返回的ArrayList是满足要求的数字但不一定有序(因为数组堆不一定有序),返回这个ArrayList,最后判题系统应该会排序后来判断结果对不对。
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()) {
            list.add(it.next());
        }
        return list;
    }
} 
方法二:手写最大堆实现(绝对比PriorityQueue优)
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) {
            list.add(target[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;
    }
}



编辑于 2018-12-30 18:03:22 回复(1)
这道题显然用priority_queue实现,复杂度O(nlogk),加入使用vector作为hash那么是O(n*k),如果使用sort复杂度是O(nlogn),此外边界条件调了我很久if(input.size() < k || k <= 0), 
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;
        
    }
};

发表于 2018-01-13 09:39:49 回复(1)
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++) 
			aList.add(input[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;
	}
}
发表于 2015-09-02 08:36:02 回复(6)
Java版本
解法一:基于堆的解法
创建大小为k的数组,基于堆排序的原理来设计数组为最大堆
    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--){
            adjustHeap(numbers,i,k-1);//将数组构造成最大堆形式
        }
        for(int i=k;i<input.length;i++){
            if(input[i]<numbers[0]){ //存在更小的数字时
                numbers[0]=input[i];
                adjustHeap(numbers,0,k-1);//重新调整最大堆
            }
        }
        for(int n:numbers)
            leastNumbers.add(n);
        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;
    }

解法二:采用partition()方法
简单易懂,但是会改变输入的数组
    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++){
            leastNumbers.add(input[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;
    }

编辑于 2018-11-11 22:49:24 回复(3)
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++){
    		set.add(input[i]);
    	}
    	Iterator<Integer> it = set.iterator();  
    	while (it.hasNext()) {  
    	  int x=it.next();
    	  list.add(x);
    	}  
    	for(int i=0;i<k;i++){
    		list2.add(list.get(i));
    	}
    	return list2;
    }
}

发表于 2016-08-23 10:10:28 回复(6)

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

解题思路

对于这种不变的数组,第一种思路是快速排序,然后找出前几个数即可,这种方法的时间复杂度为nlogn。这里我用的快排思想主要是三路快排,即荷兰国旗问题的演变。

第二种更优的思路是堆排,因为找到前k个数字的时间复杂度为nlogk

这里我用的是最小堆,因为根据题意是要快速找出前n个较小的数字,大顶堆最先找到的是最大的值,那么最终要nlogn的时间复杂度才能求出前k个最小值。显然用小顶堆是比较合适的。

下面的快排和堆排都是比较模板化的写法,虽然看起来有点长,但是我感觉思路是比较清晰的。

我的答案

快速排序:

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++){
            res.add(input[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那么直接返回
        res.add(arr[heapSize]);
        if(res.size() == k){
            return;
        }
        while(heapSize > 0){
            //在对[0,heapSize]间构建最小堆,每一轮都找到最小值,然后交换到最后
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
            //每次都将堆中最小的数拿到heapSize索引处,所以直接添加进结果集中,结果集大小为k了则立即结束
            res.add(arr[heapSize]);
            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;
    }
}
编辑于 2019-03-12 15:45:32 回复(0)
//堆排序,复杂度是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--){
            adjustHeap(input,i,k-1);
        }
        //我们前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;
                adjustHeap(input,0,k-1);
                
            }
        }
        //我们将调整好的前k个数放进链表里面
        for(int i=0;i<k;i++){
            result.add(input[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;
    }
}

发表于 2017-01-06 19:36:21 回复(4)
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;
	}
};

发表于 2016-07-31 23:46:48 回复(4)
首先得说明一点,出题的作者不太负责任,k为0还可以理解,但k超过了数组长度,还是返回空链表,没有任何道理啊,最起码要在题目要求中说明吧。。。
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--);
				list.add(j + 1, input[i]);
			}
			
		}
		// 将多于k的部分去除掉
		while (list.size() > k) {
			list.remove(k);
		}
		
		return list;
    }
}

发表于 2015-11-08 20:27:32 回复(1)
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++) {
		list.add(input[i]);
	     }
             	return list; 
            } 
    }
}

编辑于 2016-03-28 15:52:20 回复(4)
python solution 1  
        
def GetLeastNumbers_Solution(self, i, k):
        if k > len(i):
            return []
        return sorted(i)[0:k]


python solution 2

import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput):
            return []
        return heapq.nsmallest(k, tinput)

c++
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
           vector<int> n;
           if(k > input.size())return n;
           sort(input.begin(), input.end());
           while(k){
               n.insert(n.begin(), input[k-1]);
               k--;
           }
           return n;
    }

编辑于 2016-07-01 11:11:44 回复(5)