牛客题目——最小的K个数_给定一个长度为n的可能有重复值的数组

---

题目描述

给定一个长度为n的可能有重复值的数组，找出其中不去重的最小的k个数。例如数组元素是4,5,1,6,2,3,7,8这8个数字，则最小的4个数字是1,2,3,4（任意顺序皆可）。
要求：空间复杂度O(n)，时间复杂度O(nlogn)。

示例
输入：[0,1,2,1,2],3
返回值：[0,1,1]

解题思路

先排序，后取前n个数就是所求结果
快排、冒泡、归并、堆排序都可以
基于堆排序的做法如下：

• 首先创建大小为k的数组，将其调整成大根堆；
• 遍历从k+1下标开始的整数，如果存在更小的数字时，将其与堆的根交换，再调整为大根堆；
• 重复上述操作，知道遍历完n个数，前k个数即为结果。

代码实现

import java.util.ArrayList;
public class Solution {
    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;
        //用于存放最小的k个数，多申请一个单元，使得结点序号从1开始
        int[] numbers = new int[k+1];
        for(int i=1;i<k+1;i++)
            numbers[i] = input[i-1];
        //初始化最大堆
        for(int i = k/2;i>=1;i--)
            heapAdjust(numbers,i,k);
        //当输入中存在更小的数字时，重新调整最大堆
        for(int i=k;i<input.length;i++){
            if(input[i] < numbers[1]){
                numbers[1] = input[i];
                heapAdjust(numbers,1,k);
            }
        }
        for(int i=1;i<=k;i++){
            leastNumbers.add(numbers[i]);
        }
        return leastNumbers;
        
    }
    //最大堆的调整方法
    public void heapAdjust(int[] array,int start,int end){
        int temp = array[start];
        for(int j=start*2;j<=end;j*=2){
            //筛选出大孩子结点
            if(j<end && array[j]<array[j+1]) j++;
            if(temp>=array[j]) break;
            //向下筛选，将大结点调整到start位置
            array[start] = array[j];
            start = j;
        }
        array[start] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# python，归并排序实现
class Solution:
    def merge(self,array,low,mid,high):
        temp = []
        p1 = low
        p2 = mid+1
        while p1<=mid and p2<=high:
            if array[p1] <= array[p2]:
                temp.append(array[p1])
                p1 += 1
            else:
                temp.append(array[p2])
                p2+=1
        while p1<=mid:
            temp.append(array[p1])
            p1+=1
        while p2<=high:
            temp.append(array[p2])
            p2+=1
        for i in range(len(temp)):
            array[low+i] = temp[i]
        
    def mergeSort(self,array,low,high):
        if low < high:
            mid = (low+high)//2
            self.mergeSort(array, low, mid)
            self.mergeSort(array, mid+1, high)
            self.merge(array,low,mid,high)
            
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        self.mergeSort(input, 0, len(input)-1)
        return input[:k]
      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33