N29_输入n个整数，找出其中最小的K个数。

偏执的太偏执、 2023-08-17 17:36 165阅读 0赞

package new_offer;
    
    import java.util.ArrayList;
    
    import com.sun.net.httpserver.Authenticator.Result;
    
    /**
     * 
    输入n个整数，找出其中最小的K个数。
    例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
     * @author Sonya
     * 方法一：借助排序，排完之后想要几个有几个
     * 方法二：借助O（n）当可以修改输入数组时可用
     * 方法三:O(nlogK)算法，适合处理海量数据。
     *
     */
    public class N29_GetLeastNumbers_Solution {
    	
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        	ArrayList<Integer> result=new ArrayList<Integer>();
        	if(k>input.length)return result;
        	sort(input,0,input.length-1);
        	for(int i=0;i<k;i++) {
        		result.add(input[i]);
        	}
    		return result;
            
        }
        //快排
        public static void sort(int[] a, int low, int high) {
            if(low>=high)
                return;
            int i = low;
            int j = high;
            int key = a[i];
            while(i<j){
            	while(i<j&&a[j]>=key){
            	j--;
            	}
            	if(i<j){
            	a[i++]=a[j];
            	}
            	while(i<j&&a[i]<=key){
            	i++;
            	}
            	if(i<j){
            	a[j--]=a[i];
            	}
            	}
            a[i] = key;
            sort(a,low,i-1);
            sort(a,i+1,high);
        }
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		N29_GetLeastNumbers_Solution n29=new N29_GetLeastNumbers_Solution();
    		int []a= {4,5,1,6,2,7,3,8};
    		n29.GetLeastNumbers_Solution(a, 4);
    	   for(int i=0;i<a.length;i++) {
    		   System.out.println(a[i]);
    	   }
    		System.out.println(a);
    	}
    
    }

转载于:https://www.cnblogs.com/kexiblog/p/11151094.html