BM46 最小的K个数

题目描述

描述

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

示例1

输入：
[4,5,1,6,2,7,3,8],4 

返回值：
[1,2,3,4]

说明：
返回最小的4个数即可，返回[1,3,2,4]也可以 

示例2

输入：
[1],0

返回值：
[]

解题思路

解法1 排序然后取值

1.使用冒泡 or 快排 or 堆排序，进行数组排序
2.遍历数组，取出前面k小元素即可

解法2 时间复杂度为O(nlogk)的解法

1.使用冒泡，时间复杂度是o(n^2)，堆排序和快排的时间复杂度是O(nlogn)，解法要求的时间复杂度和快排很靠近，所以我们只需要考虑，如果优化快排
2.我们知道快排的思想，是每次选取一个基准值，然后将小于它的元素放到左边，大于它的元素放到右边，那么我们使用这个特性来优化
3.对比基准值的位置与k

• 当基准值的位置等于k时，那么直接返回即可，不需要再进行排序，因为此时数组的前k个元素尽管无序，但是已经是最小的k个元素
• 当基准值的位置大于k时，那么我们只需排序，基准值位置的前半部分即可
• 当基准值的位置小于k时，那么我们只需排序，基准值位置的后半部分即可

反复上面的三个步骤，直到k==基准值的位置

实践代码

解法 1 代码

import java.util.ArrayList;

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

        quickSort(input, 0, input.length - 1);
        k = k > input.length ? input.length : k;
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    private void quickSort(int[] input, int left, int right) {
        if (left < right) {
            int temp = input[left];
            int i = left;
            int j = right;
            while (left < right) {
                while (left < right && input[right] > temp) {
                    right--;
                }
                if (left < right) {
                    input[left] = input[right];
                }
                while (left < right && input[left] <= temp) {
                    left++;
                }
                if (left < right) {
                    input[right] = input[left];
                }
            }
            input[left] = temp;
            if (condition) {
                
            }
            quickSort(input, i, left - 1);
            quickSort(input, left + 1, j);
        }
    }

    private void bubbleSort(int[] input) {
        boolean swap = false;
        for (int i = 0; i < input.length; 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;
                    swap = true;
                }
            }
            if (!swap) {
                break;
            }
        }

    }
}

解法2 代码

import java.util.ArrayList;

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

        if (input.length > k) {
            quickSort(input, 0, input.length - 1, k);
        }
        
        k = k > input.length ? input.length : k;
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    private void quickSort(int[] input, int left, int right, int k) {
        if (left < right) {
            int temp = input[left];
            int i = left;
            int j = right;
            while (left < right) {
                while (left < right && input[right] > temp) {
                    right--;
                }
                if (left < right) {
                    input[left] = input[right];
                }
                while (left < right && input[left] <= temp) {
                    left++;
                }
                if (left < right) {
                    input[right] = input[left];
                }
            }
            input[left] = temp;
            if (left == k) {
                return;
            } else if (left < k) {
                quickSort(input, left + 1, j, k);
            } else {
                quickSort(input, i, left - 1, k);
            }
        }
    }
}