剑指offer面试题[30]-最小的k个数

客官°小女子只卖身不卖艺 2022-06-13 10:44 141阅读 0赞

## 题目描述 ##

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

分析思路：

这道题最简单的思路莫过于把输入的n个数排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度为O（*nlogn*）,这显然不是面试官满意的算法。

**解法一：O(n)的算法，只有当我们可以修改输入的数组时使用**

从上一篇博客剑指offer面试题\[30\]“数组中次数超过一半的数字”得到启发，我们同样可以基于partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边，位于数组左边的k个数字就是最小的k个数字（但这k个数字不一定都是有序的）。

完整VS测试：
    #include <iostream>
    #include <vector>
    using namespace std;
    class Solution {
    public:
    	vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    		int length = input.size();
    		if (input.empty() || length <= 0 || k > length || k <= 0)
    			return vector<int>();
    		int start = 0;
    		int end = length - 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> result;
    		for (int i = 0; i < k; i++)
    			result.push_back(input[i]);
    		return result;
    	}
    	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;
    	}
    };
    int main()
    {
    	vector<int> input;
    	vector<int> output;
    	int n = 8;
    	int k = 4;
    	for (int i = 0; i < n; i++)
    	{
    		int number;
    		cin >> number;
    		input.push_back(number);
    	}
    	Solution s;
    	output = s.GetLeastNumbers_Solution(input, k);
    	int length = output.size();
    	cout << "The small k numbers is :";
    	for (int i = 0; i < length; i++)
    	  {
    		cout << output[i] << " ";
    	  }
    	cout << endl;
    	system("pause");
    	return 0;
    }
    
    ***********************************
    过程分析：
    class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int length=input.size();
        if(input.empty()||length<=0||k>length||k<=0)
           return vector<int>(); 
        int start=0;
        int end=length-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> result;
         for(int i=0;i<k;i++)
             result.push_back(input[i]);
         return result;
     }
    
        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--;
                swap(input[low],input[high]);
                //input[low]=input[high];         //优化不必要的交换
                while(low<high&&pivot>=input[low])
                    low++;
                swap(input[low],input[high]);
                //input[high]=input[low];         //优化不必要的交换
            }
            input[low]=pivot;
            return low;
        }    
        
        
        /*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;
        }
        */
        
      /*  void swap(int *a,int *b)   //交换两个数
            {
               int temp;
               temp=*a;
               *a=*b;
               *b=temp;
            }
             
        int RandInRange(int a,int b)    //产生一个[a,b]范围内的随机整数
            {
               int c;
               c=a+rand()%(b-a+1);
               return c;
            }
        
        int partition(vector<int> &data,int length,int start,int end)    //partition函数是为了找出数组中第K大的数字 
           {
              if(data.empty()||length<0||start<0||end>=length)
                  return 0;  //throw new std::exception("Invakid Parameters");
              int index=RandInRange(start,end);          
              swap(&data[index],&data[end]);   
              int small=start-1;
              for(index=start;index<end;++index)
                {
                   if(data[index]<data[end])
                     {
                       ++small;
                       if(small!=index)
                            swap(&data[index],&data[small]); 
                     }
                }
               ++small;
               swap(&data[small],&data[end]); 
    
               return small;
           }
         */
    };
    ***********************************