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

这是qklbishe.com第4541 篇笔试面试资料
提供答案分析,通过本文《输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

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

Python

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

方法一:蒂姆排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         if tinput == [] or k > len(tinput):             return []         tinput.sort()         return tinput[: k]
方法二:快速排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def quick_sort(lst):             if not lst:                 return []             pivot = lst[0]             left = quick_sort([x for x in lst[1: ] if x < pivot])             right = quick_sort([x for x in lst[1: ] if x >= pivot])             return left + [pivot] + right          if tinput == [] or k > len(tinput):             return []         tinput = quick_sort(tinput)         return tinput[: k]
方法三:归并排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def merge_sort(lst):             if len(lst) <= 1:                 return lst             mid = len(lst) // 2             left = merge_sort(lst[: mid])             right = merge_sort(lst[mid:])             return merge(left, right)         def merge(left, right):             l, r, res = 0, 0, []             while l < len(left) and r < len(right):                 if left[l] <= right[r]:                     res.append(left[l])                     l += 1                 else:                     res.append(right[r])                     r += 1             res += left[l:]             res += right[r:]             return res         if tinput == [] or k > len(tinput):             return []         tinput = merge_sort(tinput)         return tinput[: k]
方法四:堆排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def siftup(lst, temp, begin, end):             if lst == []:                 return []             i, j = begin, begin * 2 + 1             while j < end:                 if j + 1 < end and lst[j + 1] > lst[j]:                     j += 1                 elif temp > lst[j]:                     break                 else:                     lst[i] = lst[j]                     i, j = j, 2 * j + 1             lst[i] = temp          def heap_sort(lst):             if lst == []:                 return []             end = len(lst)             for i in range((end // 2) - 1, -1, -1):                 siftup(lst, lst[i], i, end)             for i in range(end - 1, 0, -1):                 temp = lst[i]                 lst[i] = lst[0]                 siftup(lst, temp, 0, i)             return lst          if tinput == [] or k > len(tinput):             return []         tinput = heap_sort(tinput)         return tinput[: k]
方法五:冒泡排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def bubble_sort(lst):             if lst == []:                 return []             for i in range(len(lst)):                 for j in range(1, len(lst) - i):                     if lst[j-1] > lst[j]:                         lst[j-1], lst[j] = lst[j], lst[j-1]             return lst          if tinput == [] or k > len(tinput):             return []         tinput = bubble_sort(tinput)         return tinput[: k]
方法六:直接选择排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def select_sort(lst):             if lst == []:                 return []             for i in range(len(lst)-1):                 smallest = i                 for j in range(i, len(lst)):                     if lst[j] < lst[smallest]:                         smallest = j                 lst[i], lst[smallest] = lst[smallest], lst[i]              return lst          if tinput == [] or k > len(tinput):             return []         tinput = select_sort(tinput)         return tinput[: k]
方法七:插入排序
# -*- coding:utf-8 -*- class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         def Insert_sort(lst):             if lst == []:                 return []             for i in range(1, len(lst)):                 temp = lst[i]                 j = i                 while j > 0 and temp < lst[j - 1]:                     lst[j] = lst[j - 1]                     j -= 1                 lst[j] = temp             return lst          if tinput == [] or k > len(tinput):             return []         tinput = Insert_sort(tinput)         return tinput[: k]

2017-07-24 11:50:16 回复(36)
C/C++

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

1、全排序  时间复杂度O(nlogn)  *通过区块链毕设学生*
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {         vector<int> res;         if(input.empty()||k>input.size()) return res;                  sort(input.begin(),input.end());                  for(int i=0;i<k;i++)             res.push_back(input[i]);                  return res;              } };
2、Partiton思想 时间复杂度O(n)   *通过VS2013,区块链毕设学生超时,很纳闷,欢迎找错*
class Solution { public:     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;     }          vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {                  int len=input.size();         if(len==0||k>len) return vector<int>();         if(len==k) return input;                  int start=0;         int end=len-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> res(input.begin(), input.begin() + k);                  return res;     }  };
3、最大堆 时间复杂度O(nlogk)  *通过VS2013,区块链毕设学生超时,很纳闷,欢迎找错*
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {          int len=input.size();         if(len<=0||k>len) return vector<int>();                  vector<int> res(input.begin(),input.begin()+k);         //建堆         make_heap(res.begin(),res.end());                  for(int i=k;i<len;i++)         {             if(input[i]<res[0])             {                 //先pop,然后在容器中删除                 pop_heap(res.begin(),res.end());                 res.pop_back();                 //先在容器中加入,再push                 res.push_back(input[i]);                 push_heap(res.begin(),res.end());             }         }         //使其从小到大输出         sort_heap(res.begin(),res.end());                  return res;              } };
4、红黑树:multiset集合  利用仿函数改变排序顺序 时间复杂度O(nlogk)  *通过区块链毕设学生*
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {         int len=input.size();         if(len<=0||k>len) return vector<int>();                  //仿函数中的greater<T>模板,从大到小排序         multiset<int, greater<int> > leastNums;         vector<int>::iterator vec_it=input.begin();         for(;vec_it!=input.end();vec_it++)         {             //将前k个元素插入集合             if(leastNums.size()<k)                 leastNums.insert(*vec_it);             else             {                 //第一个元素是最大值                 multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();                 //如果后续元素<第一个元素,删除第一个,加入当前元素                 if(*vec_it<*(leastNums.begin()))                 {                     leastNums.erase(greatest_it);                     leastNums.insert(*vec_it);                 }             }         }                  return vector<int>(leastNums.begin(),leastNums.end());      } };

2016-07-28 09:54:57 回复(87)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 披萨大叔
用最大堆保存这k个数,每次只和堆顶比,如果比堆顶小,删除堆顶,新数入堆。
import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Comparator; public class Solution {    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {        ArrayList<Integer> result = new ArrayList<Integer>();        int length = input.length;        if(k > length || k == 0){            return result;        }         PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {              @Override             public int compare(Integer o1, Integer o2) {                 return o2.compareTo(o1);             }         });         for (int i = 0; i < length; i++) {             if (maxHeap.size() != k) {                 maxHeap.offer(input[i]);             } else if (maxHeap.peek() > input[i]) {                 Integer temp = maxHeap.poll();                 temp = null;                 maxHeap.offer(input[i]);             }         }         for (Integer integer : maxHeap) {             result.add(integer);         }         return result;     } }

2016-08-12 10:55:00 回复(72)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 HelloAndroid
java实现。
冒泡排序的思想,只不过最外层循环K次就可以了,也就是说不用全部排序,只挑出符合提议的K个就可以。
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> al = new ArrayList<Integer>();         if (k > input.length) { 			return al; 		} 		for (int i = 0; i < k; i++) { 			for (int j = 0; j < input.length - i - 1; j++) { 				if (input[j] < input[j + 1]) { 					int temp = input[j]; 					input[j] = input[j + 1]; 					input[j + 1] = temp; 				} 			} 			al.add(input[input.length - i - 1]); 		} 		return al;     }

2015-10-05 17:15:42 回复(27)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 MSean
思路一:利用快速排序中的获取分割(中轴)点位置函数getPartitiion
基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组的左边,比第k个数字大的所有数字都位于数组的右边。调整之后,位于数组左边的k个数字就是最小的k个数字(这k个数字不一定是排序的)。O(N)
class Solution { public:     void swap(int &fir,int &sec)     {         int temp = fir;         fir = sec;         sec = temp;     }          int getPartition(vector<int> &input,int start,int end)     {         if(input.empty() || start>end) return -1;         int temp = input[end];         int j = start - 1;         for(int i=start;i<end;++i)         {             if(input[i]<=temp)             {                 ++j;                 if(i!=j) swap(input[i],input[j]);                                 }         }         swap(input[j+1],input[end]);         return (j+1);     }              vector<int> GetLeastNumbers_Solution(vector<int> input, int k)      {         vector<int> result;                 if(input.empty() || k>input.size() || k<=0) return result;                  int start = 0;         int end = input.size()-1;         int index = getPartition(input,start,end);                  while(index != (k-1))         {             if(index > (k-1))             {                 end = index - 1;                 index = getPartition(input,start,end);             }             else             {                 start = index + 1;                 index = getPartition(input,start,end);             }         }                  for(int i=0;i<k;++i)         {             result.push_back(input[i]);         }                  return result;     } };
这种思路虽时间复杂度不错,但会修改输入数组,且一般也不易想到。更容易想到的是利用堆排序。
思路二:利用堆排序,O(N logK),适合处理海量数据
(1) 遍历输入数组,将前k个数插入到推中;(利用multiset来做为堆的实现)
(2) 继续从输入数组中读入元素做为待插入整数,并将它与堆中最大值比较:如果待插入的值比当前已有的最大值小,则用这个数替换当前已有的最大值;如果待插入的值比当前已有的最大值还大,则抛弃这个数,继续读下一个数。
这样动态维护堆中这k个数,以保证它只储存输入数组中的前k个最小的数,最后输出堆即可。
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k)     {         vector<int> result;         int len = input.size();         if(input.empty() || k<=0 || len < k) return result;                  multiset<int, greater<int> > leastNumbers; // 从大到小排序         multiset<int, greater<int> >::iterator iterGreater; // 定义迭代器                  vector<int>::iterator iter = input.begin();         for(; iter != input.end(); ++iter)         {             // 将前k个数直接插入进multiset中,注意是小于K             if(leastNumbers.size() < k)             {                 leastNumbers.insert(*iter);             }             else             {                 // 因为设置的从大到小排序,故multiset中第一个位置的元素即为最大值                 iterGreater = leastNumbers.begin();                                  // 如果input中当前元素比multiset中最大元素小,则替换;即保持multiset中这k个元素是最小的。                 if(*iter < *(leastNumbers.begin()))                 {                     // 替换掉当前最大值                     leastNumbers.erase(iterGreater);                      leastNumbers.insert(*iter);                 }             }         }                  for(iterGreater = leastNumbers.begin();iterGreater!=leastNumbers.end();++iterGreater)         {             result.push_back(*iterGreater); // 将multiset中这k个元素输出         }                  return result;     } };

2016-08-23 20:13:01 回复(16)
Java

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

Sorting O(nlogn)

Time complexity is O(nlogn)

public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {         ArrayList<Integer> res = new ArrayList<>();         if (input == null || k <= 0 || k > input.length) {             return res;         }         Arrays.sort(input);         for (int i = 0; i < k; i++) {             res.add(input[i]);         }         return res;     } }

PriorityQueue O(nlogk) 

使用PriorityQueue当作Heap,每次返回最大的值。
Time complexity is O(nlogk) 

public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {         ArrayList<Integer> res = new ArrayList<>();         if (input == null || k <= 0 || k > input.length) {             return res;         }         Queue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());          for (int i = 0; i < input.length; i++) {              if (queue.size() < k) {                 queue.add(input[i]);             } else {                 if (input[i] < queue.peek()) {                     queue.remove();                     queue.add(input[i]);                 }             }         }         while (!queue.isEmpty()) {             res.add(queue.remove());         }         return res;     } }

2017-08-02 20:30:25 回复(5)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 renhao426
/* *基于堆排序算法,构建最大堆。时间复杂度为O(nlogk) *如果用快速排序,时间复杂度为O(nlogn); *如果用冒泡排序,时间复杂度为O(n*k) */ 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 || input.length<k){             return list;         }         //构建最大堆         for(int len=k/2-1; len>=0; len--){             adjustMaxHeapSort(input,len,k-1);         }         //从第k个元素开始分别与最大堆的最大值做比较,如果比最大值小,则替换并调整堆。         //最终堆里的就是最小的K个数。         int tmp;         for(int i=k; i<input.length; i++){             if(input[i]<input[0]){                 tmp=input[0];                 input[0]=input[i];                 input[i]=tmp;                 adjustMaxHeapSort(input,0,k-1);             }         }         for(int j=0; j<k; j++){             list.add(input[j]);         }         return list;     }          public void adjustMaxHeapSort(int[] input, int pos, int length){         int temp;         int child;         for(temp=input[pos]; 2*pos+1<=length; pos=child){             child=2*pos+1;             if(child<length && input[child]<input[child+1]){                 child++;             }             if(input[child]>temp){                 input[pos]=input[child];             }else{                 break;             }         }         input[pos]=temp;     } }

2016-07-27 22:12:55 回复(22)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 绿叶萌飞
第一种方法,用优先级队列构造出最大堆,然后不断更新最大堆,每次只和堆顶比,如果比堆顶小,删除堆顶,新数入堆。但是这里利用集合并不好,手写最大堆会比这个更优,因为在超过k个数的时候,优先级队列需要poll和offer操作,poll会下沉恢复堆有序(从堆顶往下一个个比较,相当于把堆顶往下沉,然后到合适位置,堆顶下沉只会赋值一次,并不是下沉的时候比较交换),offer会上升恢复堆有序(从堆底往上一个个比较,相当于把堆底往上浮,堆底上浮只会赋值一次到合适位置,并不是上浮的时候比较交换),而如果手写堆实现的话,仅仅只需要将堆顶元素替换再下沉,就没有了上升恢复堆有序的环节。如果是100W个数找最小的5个数,假如情况比较糟糕,每次都需要更新最大堆堆顶,如果那么使用PriorityQueue将要多做999995(99W近100W)次上升恢复堆有序的操作。可以看一下PriorityQueue的源码就知道。
并且最后迭代的时候要么foreach要么iterator,本质就是iterator迭代。为什么不用for循环去list.add(queue.poll())?虽然也可以出结果,但是queue的poll方***有下沉恢复堆有序操作,而iterator不会,仅仅是遍历数组。最后返回的ArrayList是满足要求的数字但不一定有序(因为数组堆不一定有序),返回这个ArrayList,最后判题系统应该会排序后来判断结果对不对。
import java.util.ArrayList; import java.util.Comparator; import java.util.Iterator; import java.util.PriorityQueue; public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> list = new ArrayList<Integer>();         // [4,5,1,6,2,7,3,8],0         if (input == null || k > input.length || k <= 0)    return list;         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){             public int compare(Integer i1, Integer i2) {                 return i2.compareTo(i1);             }         });         int len = input.length;         for (int i = 0; i < len; ++i) {             if (queue.size() != k) {                 queue.offer(input[i]);             } else if (queue.peek() > input[i]) {                 queue.poll();                 queue.offer(input[i]);             }         }         Iterator<Integer> it = queue.iterator();         while (it.hasNext()) {             list.add(it.next());         }         return list;     } } 
方法二:手写最大堆实现(绝对比PriorityQueue优)
import java.util.ArrayList;  public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {         ArrayList<Integer> list = new ArrayList<Integer>();         // [4,5,1,6,2,7,3,8],0         if (input == null || k > input.length || k <= 0)             return list;         int[] target = new int[k];         int len = input.length;         for (int i = 0; i < len; ++i) {             if (i < k) {                 target[i] = input[i];                 heapInsertSiftUp(target, i, target[i]);             } else {                 if (target[0] > input[i]) { // 最大堆下沉                     target[0] = input[i];                     siftDown(target, 0, target[0]);                     // 相比优先级队列,这里不会offer操作(里面有上浮),少了一步上浮调整,效率高了不止一丁点                 }             }         }         for (int i = 0; i < k; ++i) {             list.add(target[i]);         }         return list;     }      private void heapInsertSiftUp(int[] target, int index, int x) {         while (index > 0) {             int parent = (index - 1) >>> 1;             if (greater(x, target[parent])) {                 target[index] = target[parent]; // 往下拉,避免直接上浮覆盖前面的值                 index = parent;             } else {                 break;             }         }         target[index] = x;     }      private boolean greater(int i, int j) {         return i > j;     }      private void siftDown(int[] target, int k, int x) {         int half = target.length >>> 1;         while (k < half) {             int child = (k << 1) + 1; // 默认先左孩子             int big = target[child];             int right = child + 1;             if (right < target.length && greater(target[right], big)) {                 big = target[right];                 child = right; // 可以直接一步big = target[child = right];             }             if (greater(x, big)) // x比子节点中的最大值还大,已经是大顶堆了                 break; // 往上拉不动了,准备退出把最初堆顶的结点赋值到上一个结点             target[k] = big; // 往上拉             k = child;         }         target[k] = x;     } } 
附上我的博客:https://blog.csdn.net/qq_34115899/article/details/85398427

2018-12-30 18:03:22 回复(10)
Python

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 什么时候才能成为红名大佬

so还是老一套,一定要记住partition函数咋写!!! import random class Solution:     def GetLeastNumbers_Solution(self, tinput, k):         # write code here         n = len(tinput)         if n<=0 or k>n:             return []         if k==0:             return []         start = 0         end = n-1         index = self.partition(tinput,start,end)         while index != k-1:             if index >k-1:                 end = index - 1                 index = self.partition(tinput,start,end)             else:                 start = index +1                 index = self.partition(tinput,start,end)         res = tinput[:k]         res=sorted(res)         return res      def partition(self,arr,start,end):         if start==end:             p=start         else:             p = random.randrange(start,end)         arr[p],arr[end]=arr[end],arr[p]         small = start-1         for i in range(start,end):             if arr[i]<arr[end]:                 small+=1                 if small != i:                     arr[small],arr[i]=arr[i],arr[small]         small +=1         arr[small],arr[end]=arr[end],arr[small]         return small

2017-08-27 22:04:09 回复(0)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 成铭
这道题显然用priority_queue实现,复杂度O(nlogk),加入使用vector作为hash那么是O(n*k),如果使用sort复杂度是O(nlogn),此外边界条件调了我很久if(input.size() < k || k <= 0), 
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {         priority_queue<int> Q;          vector<int> res;         if(input.size() < k || k <= 0) return res;         for(int i = 0; i < input.size(); ++i){             if(Q.size() < k) Q.push(input[i]);             else if(input[i] < Q.top()){                 Q.pop(); Q.push(input[i]);             }          }         while(!Q.empty()){    res.push_back(Q.top());    Q.pop();         }         return res;              } };

2018-01-13 09:39:49 回复(2)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 datong
使用简单粗暴的全部排序的方法并不能取得很好的性能,因为只要求k个数,所以使用最小堆就可以了。
(如果是要取最大值就是用最大堆)

class Solution { private:      void heapSort(vector<int> &input, int root, int end){       	for(int j = end -1; j >= root; j --){             int parent = (j + root -1)/2;             if(input[parent] > input[j]){                 int temp = input[j];                 input[j] = input[parent];                 input[parent] = temp;             }         }         }      public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {         vector<int> result ;         if(k > input.size()) return result;         for(int i = 0; i < k ; i ++){             heapSort(input,i,input.size());             result.push_back(input[i]);         }         return result;     } };

2015-09-04 20:31:20 回复(25)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 赖永华
Java版本
解法一:基于堆的解法
创建大小为k的数组,基于堆排序的原理来设计数组为最大堆
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> leastNumbers = new ArrayList<Integer>();         while(input==null || k<=0 || k>input.length)             return leastNumbers;         int[] numbers=new int[k];  //用于放最小的k个数         for(int i=0;i<k;i++)             numbers[i]=input[i];//先放入前k个数         for(int i=k/2-1;i>=0;i--){             adjustHeap(numbers,i,k-1);//将数组构造成最大堆形式         }         for(int i=k;i<input.length;i++){             if(input[i]<numbers[0]){ //存在更小的数字时                 numbers[0]=input[i];                 adjustHeap(numbers,0,k-1);//重新调整最大堆             }         }         for(int n:numbers)             leastNumbers.add(n);         return leastNumbers;     }          //最大堆的调整方法,忘记时可以复习一下堆排序。     private void adjustHeap(int[] arr,int start,int end){         int temp=arr[start];         int child=start*2+1;         while(child<=end){             if(child+1<=end && arr[child+1]>arr[child])                 child++;             if(arr[child]<temp)                 break;             arr[start]=arr[child];             start=child;             child=child*2+1;         }         arr[start]=temp;     } 
解法二:采用partition()方法
简单易懂,但是会改变输入的数组
    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {         ArrayList<Integer> leastNumbers = new ArrayList<Integer>();         while(input==null || k<=0 || k>input.length)             return leastNumbers;         int start=0;         int end=input.length-1;         int index=partition(input,start,end);         while(index!=k-1){             if(index<k-1){                 start=index+1;                 index=partition(input,start,end);             }else{                 end=index-1;                 index=partition(input,start,end);             }         }         for(int i=0;i<k;i++){             leastNumbers.add(input[i]);         }         return leastNumbers;     }          private int partition(int[] arr, int start,int end){         int pivotKey=arr[start];         while(start<end){             while(start<end && arr[end]>=pivotKey)                 end--;             swap(arr,start,end);             while(start<end && arr[start]<=pivotKey)                 start++;             swap(arr,start,end);         }         return start;     }          private void swap(int[] arr, int i,int j){         int temp=arr[i];         arr[i]=arr[j];         arr[j]=temp;     } 

2018-11-11 22:49:24 回复(4)
Java

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

题目描述

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

解题思路

对于这种不变的数组,第一种思路是快速排序,然后找出前几个数即可,这种方法的时间复杂度为nlogn。这里我用的快排思想主要是三路快排,即荷兰国旗问题的演变。

第二种更优的思路是堆排,因为找到前k个数字的时间复杂度为nlogk

这里我用的是最小堆,因为根据题意是要快速找出前n个较小的数字,大顶堆最先找到的是最大的值,那么最终要nlogn的时间复杂度才能求出前k个最小值。显然用小顶堆是比较合适的。

下面的快排和堆排都是比较模板化的写法,虽然看起来有点长,但是我感觉思路是比较清晰的。

我的答案

快速排序:

import java.util.ArrayList; public class Solution {     public ArrayList GetLeastNumbers_Solution(int [] input, int k) {         ArrayList res = new ArrayList();         if(k > input.length || k == 0){             return res;         }         //快排         quick_sort(input,0,input.length-1);         for(int i=0;i<k;i++){             res.add(input[i]);         }         return res;     }     //只要low<high就满足递归条件     private void quick_sort(int[] arr,int low,int high){         if(low < high){             //三色国旗,每次partion之后实现将小于基准数和大于基准数的值想办法搞到两边去             //返回的数组是一个长度为2的数组,分别放等于基准数的起始坐标和终止坐标             int[] p = partion(arr,low,high);             //对小于基准数的地方再次递归来搞成三色国旗             quick_sort(arr,low,p[0]-1);             //对大于基准数的地方也再次递归搞成三色国旗             quick_sort(arr,p[1]+1,high);         }     }     //三色国旗,尤其注意的是下标     private int[] partion(int[] arr,int low,int high){         int less = low - 1;         int more = high + 1;         int curr = low;         int num = arr[curr];         while(curr < more){             //小于基准值则跟++less交换,大于基准值则跟--more交换,相等则不管,继续前进             if(arr[curr] < num){                 swap(arr,++less,curr++);             }else if(arr[curr] > num){                 swap(arr,curr,--more);             }else{                 curr++;             }         }         return new int[]{less,more};     }     private void swap(int[] arr, int i, int j) {         int tmp = arr[i];         arr[i] = arr[j];         arr[j] = tmp;     } }

堆排来实现:

import java.util.ArrayList; public class Solution {     ArrayList res = new ArrayList();     public ArrayList GetLeastNumbers_Solution(int [] input, int k) {         //由于是找前k个数字,是比较小的,所以适合用小跟堆来解决         //因为大根堆先得到的是最大值,时间复杂度无法达到理想的nlogk         //整个过程是对数组进行操作的,但是与操作一颗二叉树是一样的,因为二叉堆是可以用数组来表示的         //数组的第一个元素就是二叉堆的root         //我们要保证是最小堆,那么每次从root拿到的数必然是最小的数         //root提取出来之后,将root和最后一个数交换后需要重新调整堆维持堆的性质         if(k == 0 || k > input.length){             return res;         }         heapSort(input,k);         return res;     }     private void heapSort(int[] arr,int k){         if(arr == null || arr.length < 2){             return;         }         //初步构建起一个最小堆,此时root是最小的一个数         for(int i=0;i<arr.length;i++){             heapInsert(arr,i);         }         int heapSize = arr.length;         swap(arr,0,--heapSize);         //将最小的数此时也放进list中,如果k恰好为1那么直接返回         res.add(arr[heapSize]);         if(res.size() == k){             return;         }         while(heapSize > 0){             //在对[0,heapSize]间构建最小堆,每一轮都找到最小值,然后交换到最后             heapify(arr,0,heapSize);             swap(arr,0,--heapSize);             //每次都将堆中最小的数拿到heapSize索引处,所以直接添加进结果集中,结果集大小为k了则立即结束             res.add(arr[heapSize]);             if(res.size() == k){                 return;             }         }     }     //初步构建最小堆,即构建完毕之后root为堆中最小值     private void heapInsert(int[] arr,int i){         while(arr[i] < arr[(i-1)/2]){             //如果比它的父亲小则与父亲交换             swap(arr,i,(i-1)/2);             i = (i-1)/2;         }     }     //上浮过程,每次将root和最后一个数字进行交换,然后重新构建最小堆     private void heapify(int[] arr,int index,int heapSize){         int left = index * 2 + 1;         while(left < heapSize){             //如果右子节点也没有越界的话,则从左右中挑出一个最小值             int least = left+1 < heapSize && arr[left+1]<arr[left] ? left+1 : left;             //再与当前结点做比较             int minIndex = arr[index] < least ? index : least;             //最小的就是index的话,则不用再比较了,已经是最小值了             if(minIndex == index){                 break;             }             //不是的话,则要进行交换             swap(arr,index,least);             index = minIndex;             left = index * 2 + 1;         }     }     private void swap(int[] arr, int i, int j) {         int tmp = arr[i];         arr[i] = arr[j];         arr[j] = tmp;     } }

2019-03-12 15:45:32 回复(0)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 腌臜苟且
 import java.util.ArrayList; public class Solution {     public ArrayList GetLeastNumbers_Solution(int [] input, int k) { 		ArrayList aList = new ArrayList(); 		if(input.length == 0 || k > input.length || k <= 0) 			return aList; 		int low = 0; 		int high = input.length-1; 		int index = Partition(input,k,low,high); 		while(index != k-1){ 			if (index > k-1) { 				high = index-1; 				index = Partition(input,k,low,high); 			}else{ 				low = index+1; 				index = Partition(input,k,low,high); 			} 		} 		for (int i = 0; i < k; i++)  			aList.add(input[i]); 		return aList;     } 	 	int Partition(int[] input,int k,int low,int high){ 		int pivotkey = input[k-1]; 		swap(input,k-1,low); 		while(low < high){ 			while(low < high && input[high] >= pivotkey) 				high--; 			swap(input,low,high); 			while(low < high && input[low] <= pivotkey) 				low++; 			swap(input,low,high); 		} 		return low; 	}   	private void swap(int[] input, int low, int high) { 		int temp = input[high]; 		input[high] = input[low]; 		input[low] = temp; 	} } 

2015-09-02 08:36:02 回复(6)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 夜小楼Dream
#Pythonban #利用堆排序 最小堆  # -*- coding:utf-8 -*- class Solution:      def minFixHeap(self,t,i,n):         tmp = t[i]         j = i*2+1         while j < n:             if j+1 <n and t[j+1] < t[j]:                 j+=1             if t[j] >= tmp:                 break             t[i] = t[j]             i = j             j = i*2 +1         t[i] = tmp      def GetLeastNumbers_Solution(self, tinput, k):         lens = len(tinput)         if k>lens or k <0 or lens ==0:             return []          for i in range(lens/2,-1,-1):             self.minFixHeap(tinput,i,lens)          res = []         for i in range(lens-1,lens-k-1,-1):             res.append(tinput[0])             tinput[0] = tinput[i]             self.minFixHeap(tinput,0,i)         return res  t = [3,2,4,1,5] print Solution().GetLeastNumbers_Solution(t,3)

2016-11-27 21:20:23 回复(0)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 LinYu
import java.util.ArrayList; import java.util.Iterator; import java.util.TreeSet; /*  * 利用TreeSet排序并去除重复元素,利用ArrayList存储并输出  */ public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {     	ArrayList<Integer> list=new ArrayList<Integer>();     	ArrayList<Integer> list2=new ArrayList<Integer>();     	if(input==null||input.length==0||k==0||k>input.length)     		return list;     	TreeSet<Integer> set=new TreeSet<Integer>();     	for(int i=0;i<input.length;i++){     		set.add(input[i]);     	}     	Iterator<Integer> it = set.iterator();       	while (it.hasNext()) {       	  int x=it.next();     	  list.add(x);     	}       	for(int i=0;i<k;i++){     		list2.add(list.get(i));     	}     	return list2;     } }

2016-08-23 10:10:28 回复(7)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 W.sl
//堆排序,复杂度是o(nlogn),比较稳定适合大数据量的排序,如果是快排的话分的不均匀容易引起 //复杂度是o(n^2),快排的话大数据量容易引起OOM public class Solution {     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> result = new ArrayList<Integer>();         if(input==null||input.length==0||input.length<k){             return result;         }         //构建大顶堆         for(int i=k/2-1;i>=0;i--){             adjustHeap(input,i,k-1);         }         //我们前k个元素的大顶堆已经构建好了,剩下的就是其余的和大顶堆的最大值比较了         for(int i=k;i<input.length;i++){             if(input[i]<input[0]){                 int temp=input[i];                 input[i]=input[0];                 input[0]=temp;                 adjustHeap(input,0,k-1);                              }         }         //我们将调整好的前k个数放进链表里面         for(int i=0;i<k;i++){             result.add(input[i]);         }         return result;                       }                          //构建大顶堆     public  void adjustHeap(int[] input,int i,int k){         //先把最上面根节点保存了         int temp=input[i];         for(int j=i*2+1;j<=k;j=j*2+1){             //j可以等于k,但是下面的程序不能,我们还要判断j和j+1呢             if(j<k&&input[j]<input[j+1]){                 j++;             }             if(temp>input[j]){                 break;             }             input[i]=input[j];             i=j;         }         input[i]=temp;     } }

2017-01-06 19:36:21 回复(4)
C/C++

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

class Solution { public: 	int partion(vector<int>& input, int beg, int end) 	{ 		int key = input[beg]; 		while (beg < end) 		{ 			while (beg < end && input[end] >= key)end--; 			input[beg] = input[end]; 			while (beg < end && input[beg] <= key)beg++; 			input[end] = input[beg]; 		} 		input[beg] = key; 		return beg; 	} 	vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { 		if (input.size() == 0 || input.size() < k || k <= 0)             return {}; 		int pos = partion(input, 0, input.size() - 1); 		while (pos != k - 1) 		{ 			if (pos > k - 1) 				pos = partion(input, 0, pos - 1); 			else 				pos = partion(input, pos + 1, input.size() - 1); 		} 		vector<int> res(input.begin(), input.begin() + k); 		return res; 	} };

2016-07-31 23:46:48 回复(4)
Python

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

from Queue import PriorityQueue   class Solution:     def GetLeastNumbers_Solution(self, nums, k):         size = len(nums)         if k>size or k*size==0:             return []          q = PriorityQueue(k)         for num in nums:             temp = num             if q.qsize()>=k:                 temp = min(num, q.get()[1])             q.put((-temp, temp))          result = list()         while not q.empty():             result.append(q.get()[1])          return result[::-1]   if __name__ == '__main__':     k = 4; nums = [4,5,1,6,2,7,3,8]      print Solution().GetLeastNumbers_Solution(nums, k) 

2018-01-02 17:11:48 回复(0)
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 碗碗
class Solution { public:     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {         if(k<=0||input.size()<k){             input.clear();             return input;         }         sort(input.begin(),input.end());         vector<int> result;         for(int i=0;i<k;i++){             result.push_back(input[i]);         }         return result;     } }; 最简单粗暴的就是排序, 取前k个数 

2015-05-07 00:49:10 回复(1)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情