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个不一定有序）。

 import java.util.ArrayList;

 public class Solution {

     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

         ArrayList<Integer> res = new ArrayList<Integer>();

            if(k>=input.length||k==0){

             if(k==input.length){

                 for(int m=0;m<k;m++)

                 res.add(input[m]);

             }

         return res;

         }

         int start =0;

         int end = input.length-1;

         int j = partion(input,start,end);

         while(j!=k-1){

             if(j<k-1){

                 start=j+1;

                 j = partion(input,start,end);

             }

             else{

                  end=j-1;

                 j = partion(input,start,end);

             }

         }

         for(int m=0;m<k;m++)

             res.add(input[m]);

         return res;

     }

     private int partion(int a[] ,int lo,int hi){

         int i = lo;

         int j = hi+1;

         int v = a[lo];

         while(true){

             while(a[++i]<v) if(i>=hi) break;

             while(a[--j]>v) if(j<=lo) break;

             if(i>=j) break;

             swap(a,i,j);

         }

         swap(a,j,lo);

         return j;

     }

     private void swap(int[] a,int i,int j){

         int temp = a[j];

         a[j] = a[i];

         a[i] = temp;

     }

 }

20180310

 # -*- coding:utf-8 -*-

 class Solution:

     def GetLeastNumbers_Solution(self, a, k):

         # write code here

         def partation(a, lo, hi):

             if(lo > hi):

                 return

             key = a[lo]

             i = lo

             j = hi

             while(i < j):

                 while i < hi and a[i] <= key:

                     i += 1

                 while j > lo and a[j] >= key:

                     j -= 1

                 if(i<j):

                     swap(a, i, j)

             swap(a, lo, j)

             return j

         def swap(a,i,j):

             temp = a[i]

             a[i] = a[j]

             a[j] = temp

         if(k==len(a)):

             return sorted(a)

         if(k>len(a) or k ==0):

             return []

         lo = 0

         hi = len(a) - 1

         j = partation(a, lo, hi)

         while(j != a[k - 1]):

             if(j > k - 1):

                 hi = j - 1

                 j = partation(a, lo, hi)

             else:

                 lo = j + 1

                 j = partation(a, lo, hi)

         return sorted(a[:k])

巴特西

29最小的K个数

题目描述

最新文章

热门文章