剑指offer----最小的k个数----java实现

r囧r小猫 2022-09-23 08:47 15阅读 0赞

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

思路：

如果对数组按照从小到大重新排序，那么前k个就元素就是最小的，但是时间复杂度高；

可以利用快排的思想，选数组的第一个位置的数作为分界值，第一次排序后，分界点为low

（1）如果low>k-1;low之后的数，都比low位置的数大，最小的k个数在low之前，只需要对low之前的数进行排序，end=low-1;

（2）如果low<k-1,low之前的数都比low小，最小的k个数有部分在low之后，只需要对low之后的数进行排序；

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 || k<=0||k>input.length)
    	        {
    	        	return list;
    	        }
    	        int start = 0;int end = input.length - 1;
    	        subSort(input,start,end,k);  
            
    	     for (int i = 0; i < k; i++)
    		 {
    			list.add(input[i]);
    		 }
    	        return list;
    	    }
    	 private void subSort(int[] array,int start,int end,int k)
    	 {
    		 int low = -1;
    		 if(start <= end)
    		 {
    			 low = start;int high = end;
    			 int base = array[start];
    		     while(low < high)
    			 {
    			   while(low < high && array[high] > base)
    			   {
    				 high--;
    			   }
    			   if(low < high)
    			   {
    				 array[low++] = array[high];
    			   }
    			   while(low < high && array[low] <= base)
    			   {
    				   low++;
    			   }
    			   if(low < high)
    			   {
    				   array[high--] = array[low];
    			   }
    			 
    			 }
                 array[low] = base;//得到分界点，把分界点跟K-1进行对比
                 //k个数在low之前，只需要对low之前的数再排序即可
                    if(low > k - 1)
    	        	{
    	        		end = low -1;
    	        		subSort(array,start,end,k);
    	        	}
                 //k个数有部分在low之后，对low之后的排序
    	        	else if(low < k-1)
    	        	{
    	        		start = low + 1;
    	        		subSort(array,start,end,k);
    	        	}
    		 }
             		
    	 }
    }