29最小的K个数

题目描述

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

思路：

利用快速排序的partion 来解决

如果基于数字的第k个数字来调整，使得比第k个数字小的数字都位于数组的左边，比k个数字大的所有数字都位于数组右边。这样调整之后，位于数组中左边的k个数字就行最小的k个数字（这k个不一定有序）。

 1 import java.util.ArrayList;
 2 public class Solution {
 3     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
 4         ArrayList<Integer> res = new ArrayList<Integer>();
 5            if(k>=input.length||k==0){
 6             if(k==input.length){
 7                 for(int m=0;m<k;m++)
 8                 res.add(input[m]);
 9             }
10         return res;
11         }
12         
13         
14         int start =0;
15         int end = input.length-1;
16         
17         int j = partion(input,start,end);
18         while(j!=k-1){
19             if(j<k-1){
20                 start=j+1;
21                 j = partion(input,start,end);
22             }
23             else{
24                  end=j-1;
25                 j = partion(input,start,end);
26             }
27         }
28         
29         for(int m=0;m<k;m++)
30             res.add(input[m]);
31         return res;
32     }
33     private int partion(int a[] ,int lo,int hi){
34         int i = lo;
35         int j = hi+1;
36         int v = a[lo];
37         while(true){
38             while(a[++i]<v) if(i>=hi) break;
39             while(a[--j]>v) if(j<=lo) break;
40             if(i>=j) break;
41             swap(a,i,j);
42         }
43         swap(a,j,lo);
44         return j;
45     }
46     private void swap(int[] a,int i,int j){
47         int temp = a[j];
48         a[j] = a[i];
49         a[i] = temp;
50     }
51     
52 }

20180310

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3 
 4     def GetLeastNumbers_Solution(self, a, k):
 5         # write code here
 6         def partation(a, lo, hi):
 7             if(lo > hi):
 8                 return
 9             key = a[lo]
10             i = lo
11             j = hi
12             while(i < j):
13                 while i < hi and a[i] <= key:
14                     i += 1
15                 while j > lo and a[j] >= key:
16                     j -= 1
17                 if(i<j):
18                     swap(a, i, j)
19             swap(a, lo, j)
20             return j
21         def swap(a,i,j):
22             temp = a[i]
23             a[i] = a[j]
24             a[j] = temp
25             
26         if(k==len(a)):
27             return sorted(a)
28         if(k>len(a) or k ==0):
29             return []
30         lo = 0
31         hi = len(a) - 1
32         j = partation(a, lo, hi)
33         while(j != a[k - 1]):
34             if(j > k - 1):
35                 hi = j - 1
36                 j = partation(a, lo, hi)
37             else:
38                 lo = j + 1
39                 j = partation(a, lo, hi)
40         
41         return sorted(a[:k])