【排序算法运用】剑指 Offer 40. 最小的k个数-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年6月26日下午11:59

class Solution {
    // 方法一：冒泡排序，两两比较一轮确定一个数
    public int[] getLeastNumbers(int[] arr, int k) {
        int temp = 0;
        for(int i = 0; i < k; i ++){
            // 循环一轮，确定数组的最后一个数为最小值
            for(int j = 1; j < arr.length - i; j ++){
                // 保持arr始终递减
                if(arr[j] > arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        int[] res = new int[k];
        for(int i = arr.length - k; i < arr.length; i++){
            res[arr.length - i-1] = arr[i];
        }
        return res;
    }
}
class Solution {
    // 方法一：冒泡排序，两两比较一轮确定一个数
    // 方法二：快排然后取前k个
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);
    }

    public void quickSort(int[] arr,int l, int r){
        if(r <= l){
            return;
        }
        int i = l, j = r;
        while(i < j){
            // 大于等于arr[l]右指针移动
            while(i < j && arr[j] >= arr[l]){
                j --;
            }
            // 小于等于arr[l]左指针移动
            while(i < j && arr[i] <= arr[l]){
                i ++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,l);
        quickSort(arr,l,i-1);
        quickSort(arr,i+1,r);
    }

    private void swap(int[] arr,int l, int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

}

0 赞同 0 条回复

宁永久会员 2023年3月17日上午11:04

快速排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length <= 1) return arr;
        //快速排序思路解决最小k个数
        sort(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }
    void sort(int[] arr, int start, int end, int k){
        if(start >= end) return;
        int l = start, r = end;
        while(l < r){
            //如果先操作左侧可能会让大于它的元素放在开始位置
            while(l < r && arr[r] > arr[start]) r--;
            while(l < r && arr[l] <= arr[start]) l++;
            int temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
        }
        int temp = arr[start];
        arr[start] = arr[l];
        arr[l] = temp;
        if(l + 1 == k){
            return;
        }else if(l + 1 < k){
            sort(arr, l + 1, end, k);
        }else{
            sort(arr, start, l - 1, k);
        }
    }
}

优先队列实现大顶堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        if(k == 0) return res;
        //大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        for(int i = 0; i < k; i ++){
            queue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for(int i = 0; i < k; i++){
            res[i] = queue.poll();
        }
        return res;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月16日下午5:18

大根堆

时间复杂度 O(NlogK)
空间复杂度 O(K)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) return new int[0];

        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int a : arr) {
            int t = a;
            if (q.size() >= k) t = Math.min(t, q.poll());
            q.add(t);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = q.poll();
        return ans;
    }
}

快排

时间复杂度 O(N) 最坏每次只确定1个元素，K 为 N，需要递归 N 次
空间复杂度 O(N) 同理，最坏递归 N 次

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        sort(arr, 0, arr.length - 1, k);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;
    }

    private void sort(int[] a, int l, int r, int k) {
        if (l >= r) return;
        int x = a[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do { i++; } while (a[i] < x);
            do { j--; } while (a[j] > x);
            if (i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        if (j == k - 1) return;
        if (j < k - 1) sort(a, j + 1, r, k);
        if (j > k - 1) sort(a, l, j, k);
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月16日下午2:57

def getLeastNumbers(arr, k):
    ret = quickSort(arr,0,len(arr)-1,k)
    print(arr)
    if k == 0:
        return []

    else:
        if ret:
            return ret
        else:
            return arr[0:k]



# 快排（同时要剪枝）
def quickSort(arr,left,right,k):

    if left > right:
        return

    middle = partition(arr,left,right)
    # 这种情况说明排好位置的中间数和小于中间数的那一部分就是要找的答案
    if k - 1 == middle:
        return arr[:middle+1]
    # 这种情况说明要找的前k个值在middle前面
    if k - 1 < middle:
        quickSort(arr,left,middle-1,k)
    # 这种情况说明要找的前k个值在middle后面，middle前面的数已经都小于middle，只需要将middle后面的数排好顺序
    if k - 1 > middle:
        quickSort(arr,middle+1,right,k)


def partition(arr,left,right):
    middle = arr[left]
    x = left
    y = right

    while x < y:
        while x <= y and middle >= arr[x]:
            x += 1
        while x <= y and middle <= arr[y]:
            y -= 1

        if x >= y:
            break

        temp = arr[y]
        arr[y] = arr[x]
        arr[x] = temp

    # 跳出来的时候x>y,x为小于middle这一部分最右边的那一个，需要和middle交换一下位置顺序才对
    arr[left] = arr[y]
    arr[y] = middle
    return y


from heapq import *


def getLeastNumbers1(arr, k):
    return heapMethod(arr,k)
# 堆的方式(库中的堆是小根堆，这里需要将元素变成负数来实现大根堆)
def heapMethod(arr,k):
    _arr = [-1 * arr[_] for _ in range(k)]
    heapify(_arr)

    for _ in range(k,len(arr)):
        if -1 * arr[_] > nsmallest(1,_arr)[0]:
            heappop(_arr)
            heappush(_arr,-1 * arr[_])

    return [-1 * _ for _ in _arr]

0 赞同 0 条回复

庄重普通 2023年1月12日上午9:20

// 思路：
//     1.直接使用sort排序
//     2.使用快排的思想,理解为排序，不过不需要全排序，只需要找到k个值小就行
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.empty() || k == 0){
            return vector<int>{};
        }
        return quick_FInd(arr, 0, arr.size() - 1, k);
    }

    vector<int> quick_FInd(vector<int>& arr, int left, int right, int k) {
        int i = partition(arr, left, right);

        if (i + 1 == k) {
            return vector<int>(arr.begin(), arr.begin() + k);
        }
        else if (i + 1 > k) {//找到的数比k个数多
            return quick_FInd(arr, 0, i - 1, k);
        }
        else {//i + 1 < k找到的数比k个数少
            return quick_FInd(arr, i + 1, right, k);
        }
    }

    int partition(vector<int>& arr, int left, int right) {
        int pivot = arr[left];
        int l = left + 1;
        int r = right;
        while (l < r) {
            //这两个位置必须是l <= r而不能是l < r,
            while (l <= r && arr[l] <= pivot) l++;
            while (l <= r && arr[r] >= pivot) r--;
            if (l >= r) break;

            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }

        arr[left] = arr[r];
        arr[r] = pivot;
        return r;
    }
};
//时间复杂度O(n)
//空间复杂度O(logn)

0 赞同 0 条回复

波波_1936 普通 2022年12月4日下午8:32

    /**
     * 剑指 Offer 40. 最小的k个数
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        //时间复杂度O(nlgk)
        //空间复杂度O(n)
        if(k<=0){
            return new int[0];
        }
        if(arr==null|| arr.length<=k){
            return arr;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < arr.length; i++) {
            minHeap.add(arr[i]);
        }
        int[] res = new int[k];

        for (int i = 0; i < k; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }

0 赞同 0 条回复

波波_1936 普通 2022年12月4日下午8:32

    /**
     * 剑指 Offer 40. 最小的k个数
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        //时间复杂度O(nlgk)
        //空间复杂度O(n)
        if(k<=0){
            return new int[0];
        }
        if(arr==null|| arr.length<=k){
            return arr;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < arr.length; i++) {
            minHeap.add(arr[i]);
        }
        int[] res = new int[k];

        for (int i = 0; i < k; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:41

// 快速排序
func getLeastNumbers(arr []int, k int) []int {
    var quick func(nums []int, left, right int) []int
    quick = func(nums []int, left, right int) []int {
        // 递归终止条件
        if left > right {
            return nil
        }
        // 左右指针及主元
        i, j, pivot := left, right, nums[left]
        for i < j {
            // 寻找小于主元的右边元素
            for i < j && nums[j] >= pivot {
                j--
            }
            // 寻找大于主元的左边元素
            for i < j && nums[i] <= pivot {
                i++
            }
            // 交换i/j下标元素
            nums[i], nums[j] = nums[j], nums[i]
        }
        // 交换元素
        nums[i], nums[left] = nums[left], nums[i]
        quick(nums, left, i-1)
        quick(nums, i+1, right)
        return nums
    }
    nums := quick(arr, 0, len(arr)-1)
    return nums[:k]
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午5:48

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        //先进行sort，从小到大。
        // vector<int> res(k,0);
        vector<int> res;
        if(arr.size()==0||arr.size()<k) return res;
        sort(arr.begin(),arr.end());
        for(int i = 0; i < k;i++){
            res.push_back(arr[i]);
            // res[i] = arr[i];
        }
        return res;
    }
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日下午1:40

时间复杂度：期望为 O(n)

空间复杂度：期望为O(logn)

快排

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) return new int[0];
        return quickFind(arr,0,arr.length-1,k);
    }
    public int[] quickFind(int[] arr,int lo,int hi,int k) {
        int i = partition(arr,lo,hi);
        //[0,i]一共有i+1个元素，说明此时arr[i]左侧元素都比他小
        if(i + 1 == k) {
            return Arrays.copyOf(arr,k);
        }
        //左侧多了
        if(i + 1 > k) {
            return quickFind(arr,0,i-1,k);
        }else {
            //左侧少了
            return quickFind(arr,i+1,hi,k);
        }
    }
    public int partition(int[]arr ,int lo,int hi) {
        int pivot = arr[lo];
        int i = lo + 1,j = hi;
        while(i <= j) {
            //[lo,i)小于等于pivot (j,hi]大于等于pivot
            //最终停止于j
            while(i <= j && arr[i] <= pivot) i++;
            while(i <= j && arr[j] > pivot) j--;
            if(i >= j) break;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        int tmp = arr[lo];
        arr[lo] = arr[j];
        arr[j] = tmp;
        return j;
    }
}

大根堆

用一个容量为k的大根堆，每次poll最大的数，堆中保留的就是前k小。(小根堆需要把全部的元素都入堆，是O(NlogN)，不是O(NlogK))

/**
保持堆的大小为k,然后遍历数组中的数字
小于k，直接入堆
大于k，如果比堆顶还大就直接跳过
小于堆顶就先poll，在加入
 */
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0 || arr.length == 0) return new int[0];
        //默认小根堆，实现大根堆重写一下比较器
        Queue<Integer> pq = new PriorityQueue<>((v1,v2)->v2-v1);
        for(int num : arr){
            if (pq.size() < k) {
                pq.offer(num);
            }else if (num < pq.peek()){
                pq.poll();
                pq.offer(num);
            }
        }
        //返回堆中元素
        int[] ret = new int[pq.size()];
        for(int i = 0;i < ret.length;i++) {
            ret[i] = pq.poll();
        }
        return ret;
    }
}

数据有范围时直接计数O(N)

/**
保持堆的大小为k,然后遍历数组中的数字
小于k，直接入堆
大于k，如果比堆顶还大就直接跳过
小于堆顶就先poll，在加入
 */
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length == 0 || k == 0) return new int[0];
        int[] counter = new int[10001];//数据有界
        for(int num:arr){
           counter[num]++;
        }
        int[] ret = new int[k];
        int idx = 0;
        for(int i = 0;i <= 10000;) {
            if(counter[i] > 0) {
                ret[idx++] = i;
                counter[i]--;
            }else {
                i++;
            }
            if(idx == k) return ret;
        }
        return ret;
    }
}

0 赞同 0 条回复

T 普通 2022年11月29日下午4:15

快排

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        sort(arr, 0, arr.length - 1);
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public void sort(int[] arr, int l, int r) {
        if(l < r) {
            int position = partition(arr, l, r);
            sort(arr, l, position-1);
            sort(arr, position+1, r);
        }
    }

    public int partition(int[] arr, int l, int r) {
        int pivot = arr[r];
        int pointer = l;
        for(int i = l; i < r; i++) {
            if(arr[i] <= pivot) {
                if(pointer != i) {
                    int tmp = arr[i];
                    arr[i] = arr[pointer];
                    arr[pointer] = tmp;
                }
                pointer++;
            }
        }
        int tmp = arr[r];
        arr[r] = arr[pointer];
        arr[pointer] = tmp;

        return pointer;
    }
}

0 赞同 0 条回复

大宝子冲永久会员 2022年11月24日下午10:22

import java.util.PriorityQueue;

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null)
            return null;
        int[] res = new int[k];
        PriorityQueue<Integer> queue= new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                queue.offer(arr[i]);
            } else {
                if (!queue.isEmpty()&&arr[i]< queue.peek()) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }   
}

用的优先队列

0 赞同 0 条回复

你有点可爱喔普通 2022年11月24日下午9:50

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        ///
        if(arr == null ||arr.length == 0 || k==0){
            //【0，0，0，2，0，5】
            return new int[0];
        }
        return quickFind(arr,0,arr.length-1,k);
    }
     int [] quickFind(int [] arr,int left,int right,int k) {
            int num = partition(arr,left,right);
            if (k == num+1){
                return Arrays.copyOf(arr,k);
            }
            if (num+1>k){
                return quickFind(arr,0,num-1,k);
            }else{
                return quickFind(arr,num+1,right,k);
            }

    }
    //快排                           
    public int partition(int [] arr,int L,int R){
        //二分查找
        int pivot  = arr[L];
        int left = L+1,right = R;
        while(left < right){
            while(left <= right && arr[left] <= pivot){
                    left++;
            }
            //在右边
            while(left <= right && arr[right]>= pivot){
                right--;
            }
            if (left >= right){
                break;
            }
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        arr[L] = arr[right] ;
        arr[right] = pivot;
        return right;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月24日上午11:51

思路：快速排序或堆

//快速排序
//时间复杂度O(N)
//空间复杂度O(logN)
class Solution {

    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0) return new int[0];

        find(arr, 0, arr.length - 1, k - 1);

        return Arrays.copyOf(arr, k);


    }

    public void find(int[] arr, int l, int r, int k){

//
        int p = podition(arr, l, r);

        if(p == k)
            return;


        if(p > k)
            find(arr, l, p - 1, k);
        else
            find(arr, p + 1, r, k);

    }

    public int podition(int[] arr, int l, int r){
        Random ran = new Random();
        int p = l + ran.nextInt(r - l + 1);
        swap(arr, p, l);

        int i = l + 1, j = r;
        while(true){

            while(i <= j && arr[i] < arr[l])
                i ++;

            while(j >= i && arr[j] > arr[l])
                j --;

            if(i >= j) break;

            swap(arr, i, j);

            i ++;
            j --;
        }


        swap(arr, l, j);
        return j;

    }

    public void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}

//堆
//时间复杂度O(NlogK)
//空间复杂度O(k)
class Solution2 {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < k; i++) {
            pq.add(arr[i]);
        }

        for (int i = k; i < arr.length ; i++) {
            if(!pq.isEmpty() && pq.peek() > arr[i]) {
                pq.poll();
                pq.offer(arr[i]);
            }

        }

        int[] res = new int[k];
        for(int i = 0; i < k; i ++)
            res[i] = pq.poll();
        return res;

    }


}

0 赞同 0 条回复

Error 普通 2022年11月21日下午10:46

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def quick_sort(arr, l , r):
            if l>=r:
                return 
            i, j = l, r
            while i < j:
                while i < j and arr[j] >= arr[l]:
                    j -= 1
                while i < j and arr[i] <= arr[l]:
                    i += 1
                arr[i], arr[j] = arr[j], arr[i]
            arr[l], arr[i] = arr[i], arr[l]

            quick_sort(arr, l, i-1)
            quick_sort(arr, i + 1, r)

        quick_sort(arr, 0, len(arr) - 1)
        return arr[:k]

快排时间复杂度 O(log n)

0 赞同 0 条回复

lobort 普通 2022年11月21日下午7:27

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        方法一
        Arrays.sort(arr);
        return Arrays.copyOf(arr,k);

        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr,k);
    }

    public static void quickSort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        int i = left;
        int j = right;
        while(i < j){
            //必须要先减
            while(i < j && arr[j] >= arr[left]){
                j--;
            }
            while(i < j && arr[i] <= arr[left]){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,left);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月19日下午8:31

class Solution {
//使用稳定快速排序的方法。
//时间复杂度O(nlogn)
//空间复杂度O(1)
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr==null || arr.length <= 1)return arr;
        int left = 0;
        int right = arr.length - 1;
        f1(arr,left,right);
        int[] values = new int[k];
        for (int i = 0; i < k; i++) {
            values[i] = arr[i];
        }
        return values;
    }

    public void f1(int[] arr,int l,int r){
        if(l > r) return;
        int a = sort(arr,l,r);
        f1(arr,l,a - 1);
        f1(arr,a + 1,r);
    }

    public int sort(int[] arr,int l,int r){
        int left = l;
        int a = arr[l];
        while(l < r){
            while (l <= r && arr[l] <= a) l++;
            while (l <= r && arr[r] >= a) r--;
            if(l >= r) break;
            arr[l] = arr[l] ^ arr[r];              
            arr[r] = arr[l] ^ arr[r];
            arr[l] = arr[l] ^ arr[r];
        }
        arr[left] = arr[r];
        arr[r] = a;
        return r;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月19日下午3:05

C++
思路： 1. 把所有数据放在大顶堆里面
2. 大顶堆的数据的个数超过k的话，就pop出大顶堆的top，也就是比较大的数
3. 然后再遍历把大顶堆里面的数据返回就好了
class Solution {
public:
vector getLeastNumbers(vector& arr, int k) {
priority_queue<int, vector> q;
vector ans;
for(int i = 0; i < arr.size(); ++i) {
q.push(arr[i]);
while(q.size() > k) q.pop();
}
for(int i = 0; i < k; ++i) {
ans.push_back(q.top());
q.pop();
}
return ans;
}
};

0 赞同 0 条回复

So 普通 2022年11月19日下午1:01

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) {
            return new int[0];
        }
        return quickFind(arr, 0, arr.length - 1, k);
    }

    int[] quickFind(int[] arr, int left, int right, int k) {
        int i = partition(arr, left, right);
        if (i + 1 == k) {
            return Arrays.copyOf(arr, k);
        }
        if (i + 1 > k) {
            return quickFind(arr, 0, i - 1, k);
        } else {
            return quickFind(arr, i + 1, right, k);
        }
    }

    int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (i < j) {
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            while (i <= j && arr[j] >= pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

just 普通 2022年11月19日上午11:47

//大根堆
class Solution {
public:
class cmp{
public:
bool operator()(int& a,int& b){
return a<b;
}
};
vector getLeastNumbers(vector& arr, int k) {
priority_queue<int,vector ,cmp> que;
for(int i=0;i<arr.size();++i){
que.push(arr[i]);
if(que.size()>k) que.pop();
}
vector res;
while(!que.empty()){
res.push_back(que.top());
que.pop();
}
return res;

};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月18日下午9:00

快速排序该题时间复杂度为O（n）,n+n/2+n/4+…+1 = O(n),空间复杂度由于递归深度为lgn，所有空间复杂度为O（lgn）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0){
            return new int[0];
        }
        //快速排序交换元素后返回的下标加1如果是k，那就说明前k个元素是最小的k个元素
        return quickSort(arr,0,arr.length - 1,k);
    }
    int[] quickSort(int[] arr,int left,int right,int k){
        int i = partition(arr,left,right);
        if(i + 1 == k) return Arrays.copyOf(arr,k);
        if(i + 1 > k){
            return quickSort(arr,left,i - 1,k);
        }else{
            return quickSort(arr,i+1,right,k);
        }
    }
    int partition(int[] arr,int left,int right){
        int p = arr[left];
        int i = left + 1;
        int j = right;
        while(i < j){
            while(i <= j && arr[i] <= p) i++;
            while(i <= j && arr[j] >= p) j--;
            if(i >= j) break;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = p;
        return j;
    }
}

0 赞同 0 条回复

青木普通 2022年11月18日下午8:04

/**
    就简单用一下快排的做法

    时间O(nlogn)
    空间O(logn)
 */

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        QuickSort(arr, 0, arr.length-1);
        int[] ans = new int[k];
        for(int i=0; i<k; i++){
            ans[i] = arr[i];
        }
        return ans;
    }

    public void QuickSort(int[] arr, int l, int r){
        if(l>=r) return;
        int tmp = arr[l];
        int i=l, j=r;
        while(i < j){
            while(i<j && arr[j] >= arr[l]) j--;
            while(i<j && arr[i] <= arr[l]) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        arr[i] = arr[l];
        arr[l] = tmp;
        QuickSort(arr, l, i-1);
        QuickSort(arr, i+1, r);
    }
}


/**
    堆不熟，java用PriorityQueue来作为大小顶堆，用匿名内部类重写compare函数来实现大顶堆
    接着就维护一个容量为k的堆就可以了

    时间O(nlogk)
    空间O(k)

 */

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if(k==0) return vec;

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer num1, Integer num2){
                return num2 - num1;
            }
        });

        for(int i=0; i<k; i++){
            queue.offer(arr[i]);
        }

        for(int i=k; i<arr.length; i++){
            if(queue.peek() > arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        for(int i=0; i<k;i++){
            vec[i] = queue.poll();
        }

        return vec;
    }
}

0 赞同 0 条回复

【排序算法运用】剑指 Offer 40. 最小的k个数

共以下 22 个回答

大根堆

快排

# 回答此问题取消回复

【排序算法运用】剑指 Offer 40. 最小的k个数

共以下 22 个回答

大根堆

快排

# 回答此问题 取消回复

# 回答此问题取消回复