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

mpweixin用户普通 2024年4月3日下午2:42

public void quickSort(int[] strs, int low, int high) {
if (low < high) {
int middle = getMiddle(strs, low, high);
quickSort(strs, low, middle – 1);
quickSort(strs, middle + 1, high);
}
}

public int getMiddle(int[] strs, int low, int high) {
//数组的第一个数为基准元素
int temp = strs[low];
while (low < high) {
//从后向前找比基准小的数
while (low < high && strs[high] >=temp)
high–;
//把比基准小的数移到低端
strs[low] = strs[high];
//从前向后找比基准大的数
while (low < high && strs[low] <=temp)
low++;
//把比基准大的数移到高端
strs[high] = strs[low];
}
strs[low] = temp;
return low;
}
public int[] inventoryManagement(int[] stock, int cnt) {
quickSort(stock,0,stock.length-1);
return Arrays.copyOf(stock,cnt);
}
思路：快排

0 赞同 0 条回复

扣子普通 2024年3月31日下午9:49

java
class Solution{
public int[] inventoryManagement(int[] stock, int cnt){
quickSort(stock, 0, stock.length – 1);
return Arrays.copyOf(stock, cnt);
}
private void quickSort(int[] stock, int l, int r){
if(l >= r) return;
int i = l, j = r;
while(i < j){
while(i < j && stock[j] >= stock[l]) j–;
while(i < j && stock[i] <= stock[l]) i++;
swap(stock, i, j);
}
swap(stock, i, l);
quickSort(stock, l, i – 1);
quickSort(stock, i + 1, r);
}
private void swap(int[] stock, int i, int j){
int tmp = stock[i];
stock[i] = stock[j];
stock[j] = tmp;
}
}
提交
java
class Solution{
public int[] inventoryManagement(int[] arr, int k){
if(k 0){
return new int[0];
}
Queue heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

    for(int e : arr){
        if(heap.isEmpty() || heap.size() < k || e < heap.peek()){
            heap.offer(e);
        }
        if(heap.size() > k){
            heap.poll();
        }
    }

    int[] res = new int[heap.size()];
    int j = 0;
    for(int e : heap){
        res[j++] = e;
    }
    return res;
}

}
堆排序

0 赞同 0 条回复

言之命至普通 2024年3月30日上午9:22

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 开始，0～i之间一共有 i+1个数
        if(i + 1 == k){
            return Arrays.copyOf(arr, k);//copy过去
        }

        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;
    }
}

0 赞同 0 条回复

神经蛙普通 2024年3月29日上午12:14

class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
quickSort(stock, 0, stock.size() – 1);
vector res;
res.assign(stock.begin(), stock.begin() + cnt);
return res;
}
private:
void quickSort(vector& stock, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作（以 stock[l] 作为基准数）
int i = l, j = r;
while (i < j) {
while (i < j && stock[j] >= stock[l]) j–;
while (i < j && stock[i] <= stock[l]) i++;
swap(stock[i], stock[j]);
}
swap(stock[i], stock[l]);
// 递归左（右）子数组执行哨兵划分
quickSort(stock, l, i – 1);
quickSort(stock, i + 1, r);
}
};
打卡

0 赞同 0 条回复

heathhou 普通 2024年3月27日下午10:02

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
      if(stock.empty() || cnt == 0){
        return {};
      }  
      return quickFind(stock, 0, stock.size() - 1, cnt);
    }

    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]);
        }

        arr[left] = arr[j];
        arr[j] = pivot;
        return j;

    }


};

时间复杂度：O(n)
空间复杂度：O(logn)

0 赞同 0 条回复

Jimmy 普通 2024年3月27日上午11:06

时间复杂度 O(Nlog⁡N) ：库函数、快排等排序算法的平均时间复杂度为 O(Nlog⁡N) 。
空间复杂度 O(N)：快速排序的递归深度最好（平均）为 O(log⁡N) ，最差情况（即输入数组完全倒序）为 O(N)。

class Solution {

private:
    void quickSort(vector<int>& stock,int l,int r)
    {
        // 子数组长度为 1 时终止递归
        if(l>=r)return;
        // 哨兵划分操作（以 stock[l] 作为基准数）
        int i=l,j=r;
        while(i<j)
        {
            while(i<j && stock[j]>=stock[l]) j--;//从后面找，找到第一个小于基准数的位置
            while(i<j && stock[i]<=stock[l]) i++;//从前面找，找到第一个大于基准数的位置
            swap(stock[i],stock[j]);//交换位置，让小于基准数放在前面，大于基准数的放在后面
        }
        swap(stock[i],stock[l]);//交换位置，最终让左面的数都比基准数小，右面的都比基准数大
        quickSort(stock,l,i-1);//递归左面的数组
        quickSort(stock,i+1,r);//递归右面的数组
    }

public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> ans;
        quickSort(stock,0,stock.size()-1);
        for(int i=0;i<cnt;i++)
        {
            ans.push_back(stock[i]);
        }
        return ans;
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月27日上午10:44

class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
vector arr;
int n = stock.size();
quickSort(stock,0,n-1);
for(int i =0;i<cnt;i++){
arr.push_back(stock[i]);
}
return arr;
}

void quickSort(vector<int>& a, int l, int r){

    if(l<r){
        int tmp = a[l];//注意啊，选左边第一个元素为枢轴。不是a[0]
        int i = l;
        int j = r;
        while(i<j){
            while(i<j&& a[j]>=tmp) j--;
            if(i<j) a[i] = a[j];
            while(i<j&& a[i]<=tmp) i++; 
            if(i<j) a[j] = a[i];
        }
        a[i] =tmp;
        //到此处时，i在数组中间，i左边小，右边大
        quickSort(a,l,i-1);
        quickSort(a,i+1,r);
    }
}

};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月27日上午9:05

打卡

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

        for(int &x : stock) {
            pqMax.push(x);
            if(pqMax.size() > cnt) pqMax.pop();
        }
        vector<int> res;
        while(!pqMax.empty()) {
            res.emplace_back(pqMax.top());
            pqMax.pop();
        }
        return res;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月27日上午12:45

“`java
class Solution {
public int[] inventoryManagement(int[] stock, int cnt) {
quicksort(stock,0,stock.length-1,cnt);
int[] ans = new int[cnt];
for(int i = 0; i < cnt; i++){ ans[i] = stock[i]; } return ans; } private void quicksort(int[] stock,int begin,int end,int cnt){ if(begin >= end || cnt < begin) return; int key = stock[begin]; int l = begin; int r = end; while(l < r){ while(l < r && stock[r] >= key)
r–;
stock[l] = stock[r];
while(l < r && stock[l] <= key) l++; stock[r] = stock[l]; } stock[l] = key; if(cnt < l) quicksort(stock,begin,l-1,cnt); if(cnt > l) quicksort(stock,l+1,end,cnt);
}
}
时间复杂度On
空间复杂度Ologn

0 赞同 0 条回复

机电皮怪永久会员 2024年3月26日下午11:08

快速排序

“`c++
class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
if(stock.empty() == true || cnt <= 0) { return {}; } return quickfind(stock, 0, stock.size() - 1, cnt); } private: vector quickfind(vector&arr, int left, int right, int k )
{
int i = partiton(arr, left, right);
if( i + 1 k)
{
return vector(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 partiton(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;
        }

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    arr[left] = arr[j];
    arr[j] = pivot;

    return j;
}

};

“`

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月26日下午9:08

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {

        if(stock == null || stock.length == 0 || cnt==0){
            return new int[0];
        }

        return quickFind(stock,0,stock.length-1,cnt);
    }

    int[] quickFind(int[] stock,int left,int right,int cnt){
        int i = partition(stock,left,right);

        if(i+1 == cnt){
            return Arrays.copyOf(stock,cnt);
        }
        if(i+1>cnt){
            return quickFind(stock,left,i-1,cnt);
        }else{
            return quickFind(stock,i+1,right,cnt);
        }
    }

    int partition(int[] stock,int left,int right){

        int privot = stock[left];

        int i = left+1;
        int j = right;

        while(i<j){
            while(i<=j && stock[i]<=privot) i++;
            while(i<=j && stock[j]>=privot) j--;

            if(i >= j){
                break;
            }

            int temp = stock[i];
            stock[i] = stock[j];
            stock[j] = temp;

        }
        stock[left]=stock[j];
        stock[j]=privot;
        return j;

    }
}

时间复杂度：O(n)
空间复杂度：O(logn)，平均递归调用深度

0 赞同 0 条回复

紫芝普通 2024年3月26日下午8:30

思路：快排的思想

“`c++
class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
if (cnt >= stock.size()) return stock;
return quickSort(stock, cnt, 0, stock.size()-1);
}
private:
vector quickSort(vector& stock, int cnt, int left, int right) {
int i = left, j = right;
while (i < j) { while (i < j && stock[j] > stock[left]) –j;
while (i < j && stock[i] <= stock[left]) ++i; swap(stock[i], stock[j]); } swap(stock[i], stock[left]); if (i > cnt) return quickSort(stock, cnt, left, i-1);
if (i < cnt) return quickSort(stock, cnt, i+1, right); vector ans;
ans.assign(stock.begin(), stock.begin()+cnt);
return ans;
}
};
“`

0 赞同 0 条回复

Raphtalia. 普通 2024年3月26日下午8:26

class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
if(stock.size() < cnt) return vector ();
return findk(stock, 0, stock.size() – 1, cnt);
}
private:
vector findk(vector& stock, int l, int r, int cnt) {
int i = l, j = r;
while(i < j) {
while(i < j && stock[j] >= stock[l]) j –;
while(i < j && stock[i] <= stock[l]) i ++;
swap(stock[i],stock[j]);
}
swap(stock[i],stock[l]);
if(i > cnt) return findk(stock, l, i – 1, cnt);
if(i < cnt) return findk(stock, i + 1, r, cnt);
vector res;
for(int k = 0; k < i; k ++) {
res.push_back(stock[k]);
}
return res;
}
};
时间复杂度O（n），空间复杂度O（logn）

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复