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

hi 普通 2023年11月3日下午6:42

排序的做法

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> res;
        sort(stock.begin(), stock.end());
        for(int i = 0; i < cnt; i++)
        {
            res.push_back(stock[i]);
        }
        return res;
    }
};

大根堆里维护最小的几个数的做法，超过要求的个数时，大根堆会让更大的那个数出队列

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        priority_queue<int> pq;
        vector<int> res;

        for(auto x : stock)
        {
            pq.push(x);
            if(pq.size() > cnt) pq.pop();
        }

        while(pq.size()) res.push_back(pq.top()), pq.pop();
        // reverse(res.begin(), res.end());
        return res;
    }
};

0 赞同 0 条回复

桎梏普通 2023年9月13日下午10:11

//快排
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(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 quickSort(int[] arr, int left, int right) {
        if(left >= right) return;
        int p = partition(arr, left, right);
        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }

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

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

0 赞同 0 条回复

June 普通 2023年9月10日下午11:59

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr,k,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 k,int L,int R)
    {
        int n = arr.length;
        for(int i=0 ; i<n;i++)
        {
            System.out.print(arr[i]);
        }
        System.out.println();
        if (L >= R || n == k)
            return;

        int split = arr[R];
        int i=L-1;
        for(int j=L;j<=R-1;j++)
        {
            if(arr[j] <= split)
            {
                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,i+1,R);
        int pos = i + 1;

        int preNum = pos - L + 1;
        if (k == preNum)
            return;
        if (k < preNum)
        {
            quickSort(arr,k,L,pos-1);
        }
        else
        {
            quickSort(arr,k-preNum,pos+1,R);
        }
    }

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

0 赞同 0 条回复

Marshan 普通 2023年8月18日下午8:38

快排

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        //快速排序找前k小的数,当找到partition时候判断partition与k的大小,如果等于k则返回前partition个数,主要是题目没说要顺序返回
        if(arr.empty() || k == 0){
            return {};
        }

        return quickFind(arr,0,arr.size() - 1,k);
    }
    vector<int> quickFind(vector<int>& arr,int left,int right,int k){
        int mid = partition(arr,left,right);
        if(mid + 1 == k){
            return vector<int>(arr.begin(),arr.begin() + k);
        }
        else if(mid + 1 < k){
            return quickFind(arr,mid + 1,right,k);
        }
        else{
            return quickFind(arr,left,mid - 1,k);
        }
    }
    int partition(vector<int>& arr,int left,int right){
        int i = left, j = right;
        int pivot = arr[left];
        while(i < j){
            while(i < j && pivot <= arr[j]){
                j--;
            }
            if(i < j){
                swap(arr[i++],arr[j]);
            }
            while(i < j && pivot >= arr[i]){
                i++;
            }
            if(i < j){
                swap(arr[i],arr[j--]);
            }
        }

        return j;
    }
};

0 赞同 0 条回复

普通 2023年8月16日下午10:29

c++ 代码
class Solution {
public:
vector getLeastNumbers(vector& arr, int k)
{
vector res;
sort(arr.begin(),arr.end());
for(int i=0;i<k;i++)
res.push_back(arr[i]);
return res;
}
};

0 赞同 0 条回复

CKX 普通 2023年8月9日下午11:39

func getLeastNumbers(arr []int, k int) []int {
    quickSort(arr, 0, len(arr)-1, k)
    return arr[:k]
}

func partition(arr []int, left, right int) int {
    i := left
    j := right
    pivot := arr[i]
    for i < j {
        for i < j && arr[j] >= pivot {
            j--
        }
        arr[i] = arr[j]
        for i < j && arr[i] <= pivot {
            i++
        } 
        arr[j] = arr[i]
    }
    arr[i] = pivot
    return i
}

func quickSort(arr []int, i int, j int, k int) {
    if i < j {
        pivot := partition(arr, i, j)
        if pivot == k {
            return
        }
        quickSort(arr, i, pivot-1, k)
        quickSort(arr, pivot+1, j, k)
    }
}

时间O(nlogn)
空间O(n)

0 赞同 0 条回复

北辰普通 2023年8月8日下午3:07

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

        //采用大根堆，大根堆的根节点为堆中的最大值
        //堆保持k个元素，然后有元素的值小于堆顶元素，将堆顶元素弹出，加入新元素
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1,Integer num2) {
                return num2-num1;
            }
        });

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

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

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

0 赞同 0 条回复

#00456B 普通 2023年8月6日上午12:33

// class Solution {
// public:
//     //快排方法
//     vector<int> getLeastNumbers(vector<int>& arr, int k) {
//         if(arr.empty() || k == 0){
//             return {};
//         }
//         return quickFind(arr, 0, arr.size() - 1, k);
//     }

//     vector<int> quickFind(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){
//             return quickFind(arr, left, i - 1, k);
//         }
//         else{
//             return quickFind(arr, i + 1, right, k);
//         }
//     }

//     int partition(vector<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;
//             }
//             swap(arr[i], arr[j]);
//         }
//         swap(arr[j], arr[left]);
//         return j;
//     }
// };
class Solution {
public:
    //小根堆
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> que;
        for(int x:arr){
            que.push(x);
            if(que.size() > k){
                que.pop();//小根队，最上面的是最大的元素，pop
            }
        }
        vector<int> ans;
        while(!que.empty()){
            ans.push_back(que.top());
            que.pop();
        }
        return ans;
    }

};

0 赞同 0 条回复

NullPointerException 普通 2023年8月4日上午11:21

class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
// 快排优化哨兵切割
//最小的k个数哨兵下标=k-1 0 -k-1
qiege(arr,0,arr.length-1,k);
int result[] =new int[k];
for(int i=0;i<k;i++)
{
result[i]=arr[i];
}
return result;

}
public void qiege(int [] arr,int left,int right,int k)
{

    if(left<right)
    {
        int a=paixu(arr,left,right);
        if(a==k-1)
        {
            return ;
        }
        qiege(arr,left,a-1,k);
        qiege(arr,a+1,right,k);
    }
}
public int paixu(int []arr,int left,int right)
{
    int shaobin = arr[left];
    while(left<right)
    {

          while(left<right&&arr[right]>=shaobin)
        {
            right--;
        }
        arr[left]=arr[right];
        while(left<right&&arr[left]<=shaobin)
        {
            left++;
        }
        arr[right]=arr[left];

    }
    arr[left]=shaobin;
    return left;
}

}

0 赞同 0 条回复

Mby 普通 2023年8月3日下午11:34

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);
        //i+1， 是因为数组下标从0开始
        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);
        }
    }
    //找出pivot的下标以及使小于等于pivot在左边，大于等于的在右边
    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(logn)
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月2日上午11:13

快排思想：不用全部都排，只需要排好第k个小的数，那他之前的都会比他小，时间复杂度O（N）

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

    private int[] quickSearch(int[] arr, int l, int r, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(arr, l, r);
        if (j == k) {
            return Arrays.copyOf(arr, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(arr, l, j - 1, k): quickSearch(arr, j + 1, r, k);
    }

    public int partition(int[] arr, int left, int right) {
        int i = left, j = right;

        while(i < j) {
            while(i < j && arr[j] >= arr[left]) j --;
            while(i < j && arr[i] <= arr[left]) i ++;

            if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;               
            }
        }
        int temp = arr[left];   
        arr[left] = arr[i];
        arr[i] = temp;

        return i;
    }
}

堆：用大根堆来做，因为小根堆需要把元素都压入，而大根堆只需把更大的弹出，剩下的就都是前k小的数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length == 0 || k == 0) return new int[0];
        Queue pq = new PriorityQueue<>((o1,o2) -> o2 - o1);
        for(int num : arr) {
            if(pq.size() < k) {
                pq.offer(num);
            } else if(pq.peek() > num) {
                pq.poll();
                pq.offer(num);
            }
        }

        int[] res = new int[pq.size()];
        int index = 0;
        for(int i : pq) {
            res[index ++] = i;
        }
        return res;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月1日下午8:09

8.1
Day23：下面是代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);
    }
    private void quickSort(int[] arr, int l, int r){
        int i = l, j = r;
        if(l >= r) return;
        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;
            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 i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月1日下午6:47

//小顶堆
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0) return new int[0];

        PriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a, b));

        for(int num : arr){
            pq.offer(num);
        }

        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            result[i] = pq.poll();
        }

        return result;
    }
}

//大顶堆
class Solution1 {
    public int[] getLeastNumbers(int[] arr, int k) {
        // 大顶堆，堆顶是最大元素
        PriorityQueue pq = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        for (int e : arr) {
            // 每个元素都要过一遍二叉堆
            pq.offer(e);
            // 堆中元素多于 k 个时，删除堆顶元素
            if (pq.size() > k) {
                pq.poll();
            }
        }
        // pq 中剩下的是 arr 中最小的 k 个元素
        int[] res = new int[k];
        int i = 0;
        while (!pq.isEmpty()) {
            res[i] = pq.poll();
            i++;
        }
        return res;
    }
}

//快排：关键在于找到第k小的数的位置
class Solution {
    int[] res;
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0) return new int[0];
        res = new int[k];
        shuffle(arr);

        int l = 0;
        int r = arr.length - 1;

        while(l <= r){
            int idx = partition(arr, l, r);
            if(idx < k - 1){
                l = idx + 1;
            }else if(idx > k - 1){
                r = idx - 1;
            }else{
                for(int i = 0; i <= idx; i++){
                    res[i] = arr[i];
                }
                return res;
            }
        }

        return res;
    }

    private int partition(int[] arr, int l, int r){
        int i = l;
        int j = r;

        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;
            while(i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);

        return i;
    }

    //快排优化
    private void shuffle(int[] nums){
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    private void swap(int[] arr, int idx1, int idx2){
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月1日下午5:20

public int[] getLeastNumbers(int[] arr, int k) {
        // 输入：arr = [3,2,1], k = 2
        //输出：[1,2] 或者 [2,1]
        quickSort(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 quickSort(int[] arr, int left, int right) {
        if (left > right)
            return;
        int jizhun = arr[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i<j&&arr[j]>=jizhun) j--;
            while (i<j&&arr[i]<=jizhun) i++;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        arr[left] = arr[i];
        arr[i] = jizhun;

        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }

0 赞同 0 条回复

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

共以下 14 个回答

快排思想：不用全部都排，只需要排好第k个小的数，那他之前的都会比他小，时间复杂度O（N）

堆：用大根堆来做，因为小根堆需要把元素都压入，而大根堆只需把更大的弹出，剩下的就都是前k小的数

# 回答此问题取消回复

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

共以下 14 个回答

快排思想：不用全部都排，只需要排好第k个小的数，那他之前的都会比他小，时间复杂度O（N）

堆：用大根堆来做，因为小根堆需要把元素都压入，而大根堆只需把更大的弹出，剩下的就都是前k小的数

# 回答此问题 取消回复

# 回答此问题取消回复