JZ40 最小的K个数

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

解法一：sort

工作中使用该方法，面试不使用。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(input[i]);
        }
        return list;
    }
1
2
3
4
5
6
7
8

排序算法很多，出于面试考虑，先列出冒泡和快排，因为这俩面试最常见。

解法二：冒泡

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        bubbleSort(input);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(input[i]);
        }
        return list;
    }

    public void bubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析：
时间复杂度：O(N^2)，遍历数组两层
空间复杂度：O(1)，不涉及额外内存空间

解法三：快排

快排思路：找到一个基准(一般取第一个元素即可)，基准以左都比它小，基准以右都比它大，然后分别向左向右递归。

递归出口：数组长度小于1或者左边界小于0或者右边界大于数组长度或者左边界大于右边界。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        quickSort(input,0,input.length-1);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(input[i]);
        }
        return list;
    }

    // 快排
    public void quickSort(int[] arr,int low,int high){
        if(low<0||high>=arr.length||arr.length<1||low>high){
            return;
        }
        int partation = getPartation(arr,low,high);
        quickSort(arr,low,partation-1);
        quickSort(arr,partation+1,high);
    }
    private int getPartation(int[] arr,int low,int high){
        int partation = arr[high];
        while(low<high){
            while(low<high&&arr[low]<=partation){
                low++;
            }
            arr[high] = arr[low];
            while(low<high&&arr[high]>=partation){
                high--;
            }
            arr[low]=arr[high];
        }
        arr[high]=partation;
        return high;
    }
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

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(logn)

总结：
涉及数据结构：数组
涉及算法：冒泡、快排

JZ41 数据流中的中位数
题目：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

排序就不手写了，直接调包。

该题容易出错的地方是返回值为Double类型，所以当集合长度为偶数时，两个Integer类型相加再除以2还是Integer,并且还会舍去余数，所以用Double来接收，double相加还是double,除以2也是double，并且是精确的。

public class Solution {

    List<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {
    list.add(num);
    }

    public Double GetMedian() {
        Collections.sort(list);
        int size = list.size();
        if(size%2==0){
            double v1 = list.get(size/2);
            double v2 = list.get(size/2-1);
            return (v1+v2)/2;
        }else{
          return Double.parseDouble(""+list.get(size/2));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19