题解 | #最小的K个数#

最小的K个数

http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

1 思路

位图法

数据特征重复无序
容易出错位图赋值位图使用循环的边界
基础方法（依然有快排思想）才是王道，处处是经典

方法1 位图坑

累计45分钟提交 alt

方法3 利用快排的分划函数坑

轴的使用

alt

2 code

第一是直觉法位图
第二是两年前使用的高级数据结构大顶堆

c++
java
c++

class Solution {
    int bitmap[10001];
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        //不去重的K个数字
        vector<int> retV;
//         if(nullptr input){
//             return retV;
//         }
        if(0 == k ||input.size()==0){
            return retV;
        }
        int i =0;
        
        for( ; i< input.size(); i++){//ignore 0
            bitmap[input[i]]++;//基础！！！
        }
        int j=0,count =0;
        for(i=0; count<k ;i++){//i<=k && count<=k 
            for(j=0;j<bitmap[i] && count<k;j++){
                retV.push_back( i);//基础
                count++;
            }
            
        }
        
        return retV;
        
    }
};

import java.util.*;
 
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int 
[] input, int k) {
            ArrayList<Integer> res = new ArrayList<Integer>();
         
        //1:exception todo
         
        if(input == null || k<=0 || (input!=null && input.length<k ))
            return res;
         
        //2:declare maxHeap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k,
                                                                   new Comparator<Integer>(){
                                                                       @Override
                                                                       public int compare(Integer o1, Integer o2){
                                                                           return o2.compareTo(o1);
                                                                       }
                                                                   });
         //3:build maxHeap while iterate
        for(int i=0; i< input.length; i++){
            if(i<k){
                maxHeap.offer(input
[i]);
            }else if(maxHeap.peek() > input
[i]){
                maxHeap.poll();
                 
                maxHeap.offer(input
[i]);
            }
        }
 
        //4:put to result
        for(Integer i: maxHeap){
            res.add(i);
        }
        return res;
        //test case : null array&nbs***bsp;k<=0
         
        /*
不要写成 匹克了
        */
    }
}

class Solution {
public:
    

    
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
		vector<int> retV;
		if(k<=0)
		return retV;
		
		int size = input.size();
		if(size ==0)
			return retV;
		int left = 0, right = size - 1;
		while(left < right){
		//缩小窗口
			int z = FenQu(input,left,right);
			if( z+1 == k)
			{break ;}
			else if( z+1 <k){
			//find right
			left = z+1;
			}else{
			right = z;
			}
  
		}
	for(int t=0; t < k; t++){
			retV.push_back(input[t]);
    }
		return retV;
	
	}
	
    void swap(int & a ,int & b){
        int   c;
			c=a;
			a =b;
			b =c;

    }
    int FenQu(vector<int> & input, int left , int right){
        if(left>right){
            return -1;
        }
        int Zhou = input[right - 1] ;
        
        int i = left ,j=0;
        //double index 魅力
    
		// j start 容易错，允许一次自己和自己换？？？
		//j= left+1
        for(j= left ; j< right-1 ;j++){
            if( input[j] <Zhou){
                swap(input[i++] , input[j]);
            }
        }			
		swap( input[i], input[right-1]);
		
		return i;

    }
       
};