九号球普通 2023年11月28日下午8:35

“`java
//排序
class Solution {
int count = 0;
public int[] inventoryManagement(int[] stock, int cnt) {
if (stock == null || stock.length <= 0) { return new int[0]; } count = cnt; quickSort(stock, 0, stock.length - 1); int[] res = new int[cnt]; for (int i = 0; i < cnt; i++) { res[i] = stock[i]; } return res; }

public void quickSort(int[] stock, int left, int right) {
    if (left >= right || left >= count) {
        return;
    }
    int pivotI = new Random().nextInt(right - left + 1) + left;
    swap(stock, pivotI, right);
    int pivot = stock[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (stock[j] <= pivot) {
            i++;
            swap(stock, i, j);
        }
    }
    i = i + 1;
    swap(stock, i, right);
    quickSort(stock, left, i - 1);
    quickSort(stock, i + 1, right);
}

public void swap(int[] stock, int i, int j) {
    int tmp = stock[i];
    stock[i] = stock[j];
    stock[j] = tmp;
}

}

0 赞同 0 条回复

招舟子普通 2023年9月8日下午3:52

class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
return Arrays.copyOf(arr,k);
}
}
直接api

0 赞同 0 条回复

屠龙手段普通 2023年8月10日下午9:31

随机化三路快排时间复杂度O(n) 空间复杂度O(logn)

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        low, high = 0, len(arr) - 1

        def partition(arr, low, high):
            pivot_idx = random.randint(low, high)
            pivot = arr[pivot_idx]
            arr[high], arr[pivot_idx] = arr[pivot_idx], arr[high]
            smaller = low
            equal = low
            larger = high
            while equal <= larger:
                if arr[equal] > pivot:
                    arr[equal], arr[larger] = arr[larger], arr[equal]
                    larger -= 1
                elif arr[equal] == pivot:
                    equal += 1
                else:
                    arr[equal], arr[smaller] = arr[smaller], arr[equal]
                    smaller += 1
                    equal += 1
            return smaller, larger

        def quick_sort(arr, low, high):
            if low < high:
                smaller, larger = partition(arr, low, high)
                quick_sort(arr, low, smaller - 1)
                quick_sort(arr, larger + 1, high)
            return arr

        return quick_sort(arr, low, high)[:k]

堆排序时间复杂度O(nlogn) 空间复杂度 O(1)


class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def heapify(arr, start, end):
            largest = start
            left = start * 2 + 1
            right = start * 2 + 2
            if left < end and arr[largest] < arr[left]:
                largest = left
            if right < end and arr[largest] < arr[right]:
                largest = right
            if largest != start:
                arr[largest], arr[start] = arr[start], arr[largest]
                heapify(arr, largest, end)

        def heap_sort(arr):
            n = len(arr)
            for i in range(n // 2 - 1, -1, -1):
                heapify(arr, i, n)
            for i in range(n - 1, 0, -1):
                arr[0], arr[i] = arr[i], arr[0]
                heapify(arr, 0, i)
            return arr
        
        return heap_sort(arr)[:k]

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:43

“`C++
vector getLeastNumbers(vector& arr, int k) {
vector result;

// 维护一个大顶堆，堆中元素个数不超过 k
priority_queue<int, vector<int>, less<int>> heap;

// 先将前 k 个数放入堆中
for (int i = 0; i < k; i++) {
    heap.push(arr[i]);
}

// 遍历剩余的数，如果比堆顶元素小，则替换堆顶元素并调整堆
for (int i = k; i < arr.size(); i++) {
    if (arr[i] < heap.top()) {
        heap.pop();
        heap.push(arr[i]);
    }
}

// 将堆中的元素放入结果数组
while (!heap.empty()) {
    result.push_back(heap.top());
    heap.pop();
}

return result;

}

“`

0 赞同 0 条回复

BOZ 普通 2023年7月19日下午3:01

【思路】用快排思路，每次随机取一个数作为mid并将其他数分至其两侧，递归的时候需要判断mid的index与k的大小关系：若index=k则可以直接返回（此时index左侧的即为最终答案）；index<k则只需要对右侧做进一步排序；index>k则只需要对左侧做进一步排序。
【复杂度】时间复杂度O(n)，空间复杂度O(1)；如果使用堆排序思路，时间复杂度为O(nlogk)，空间复杂度O(k)

class Solution {
    int k;

    void quickSortMin(vector& arr, int left, int right) {
        if (left >= right) return;
        int mid = arr[left];
        int l = left, r = right;

        // find the position for mid
        while(l < r) {
            while(arr[r] > mid && l < r) r--;
            while(arr[l] <= mid && l < r) l++;
            if (l < r) std::swap(arr[l], arr[r]);
        }
        if (arr[l] < mid) std::swap(arr[left], arr[l]);

        // sort the left/right part if need to
        if (l < k) {                // no need to sort the left part
            quickSortMin(arr, l + 1, right);
        } else if (l > k) {         // only need to sort the left part
            quickSortMin(arr, left, l - 1);
        } else return;
    }

public:
    vector getLeastNumbers(vector& arr, int k) {
        this->k = k;
        quickSortMin(arr, 0, arr.size() - 1);
        arr.resize(k);
        return arr;
    }
};

0 赞同 0 条回复

局外人普通 2023年7月18日下午2:59

思路：快排中枢
时间复杂度O(N) 空间复杂度O(logN)

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

    public int[] quickSort(int[] arr, int low, int high, int k){
        int i=low, j=high;
        while(i<j){
            while(i<j && arr[j]>=arr[low])  j--;
            while(i<j && arr[i]<=arr[low])  i++;
            swap(arr, i, j);
        }
        swap(arr, i, low);

        if(i>k) return quickSort(arr, low, i-1, k);
        if(i<k) return quickSort(arr, i+1, high, k);
        return Arrays.copyOf(arr, k);
    }

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月16日下午11:51

时间复杂度：O(N)
空间复杂度：O(logN)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length <= k) return arr;
        // 快排
        quickSort(arr, 0, arr.length - 1, k);

        return Arrays.copyOf(arr, k);
    }


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


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

            while(i < j && arr[j] >= p){
                j--;
            }

            while(i < j && arr[i] <= p){
                i++;
            }

            if(i < j){
                swap(arr, i, j);
            }
        }
        arr[left] = arr[j];
        arr[j] = p;
        return j;
    }

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

0 赞同 0 条回复

江畅普通 2023年7月16日下午7:41

// 快排
// 时间复杂度 O(N)
// 空间复杂度 O(logN)
class Solution {
private:
    // 搜索并返回最小的 k 个数
    vector<int> quickSort(vector<int>& arr, int k, 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], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) {
            return quickSort(arr, k, l, i - 1);
        }
        if (i < k) {
            return quickSort(arr, k, i + 1, r);
        }
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }

public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k >= arr.size()) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.size() - 1);
    }
};

// 堆排序
// 时间复杂度 O(N log k)
// 空间复杂度 O(k)
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        // 大根堆，堆顶是最大元素
        priority_queue<int> pq;
        for (int e : arr) {
            // 每个元素都要过一遍二叉堆
            pq.push(e);
            // 堆中元素多于 k 个时，删除堆顶元素
            if (pq.size() > k) {
                pq.pop();
            }
        }
        // pq 中剩下的是 arr 中最小的 k 个元素
        vector<int> res(k);
        int         i = 0;
        while (!pq.empty()) {
            res[i] = pq.top();
            pq.pop();
            i++;
        }
        return res;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月16日下午3:01

快速排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length <= 1) {
            return arr;
        }
        int l = 0;
        int r = arr.length -1 ;
        quickSort(arr,l,r);
        return Arrays.copyOf(arr,k);
    }
    public void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int pivotIndex = partition(arr, l, r);
            quickSort(arr, l, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, r);
        }
    }
    public int partition(int[] arr, int l, int r) {
        int n = arr[r];
        int i = l - 1;
        for(int j = l; j < r; j++) {
            if(arr[j] <= n) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i+1];
        arr[i+1] = n;
        arr[r] = temp;
        return i+1;
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午8:03

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

        heapq.heapify(arr)
        res = []

        while k > 0:
            res.append(heapq.heappop(arr))
            k -= 1

        return res

使用heap

0 赞同 0 条回复

Jerry 普通 2023年7月15日下午10:47

// 堆
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = getTopKPriorityQueue(arr, k);

        return queue.stream().mapToInt(Integer::intValue).toArray();
    }

    private PriorityQueue<Integer> getTopKPriorityQueue(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);

        for (int num : arr) {
            queue.offer(num);
            if (queue.size() > k) queue.poll(); //删除栈顶元素
        }
        return queue;
    }
}

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

0 赞同 0 条回复

花老爷普通 2023年7月15日下午4:32

排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.stream(arr).limit(k).toArray();
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月15日上午11:13

快排

int[] res;
    int k;
    public int[] getLeastNumbers(int[] arr, int k) {
        res = new int[k];
        this.k = k;
        quickSort(arr, 0, arr.length-1);
        return res;
    }

    private void quickSort(int[] arr, int l, int r){
        if(l > r) return;
        int p = partition(arr, l, r);
        if(p < k){
            res[p] = arr[p];
        }
        if(p > k){
            quickSort(arr,l,p-1);
        }else{
            quickSort(arr,l,p-1);
            quickSort(arr,p+1,r);
        }

    }

    private int partition(int[] arr, int l, int r){
        int i = l,j = r;
        int temp = arr[l];
        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;
            while(i < j && arr[i] <= arr[l]) i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[i] = arr[l];
        arr[l] = temp;
        return i;
    }

0 赞同 0 条回复

Yodl. 普通 2023年7月14日下午9:17

//法一：堆排序 时间复杂度O(k)  空间复杂度O(n)
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

//快排  时间复杂度O(n)  空间复杂度O(logn)
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k >= arr.size()) return arr;
        return quickSort(arr, k, 0, arr.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
};

0 赞同 0 条回复

yxy 普通 2023年7月14日下午8:48

时间复杂度O(logk)+O(n)

const int N = 1e4+10;
int h[N];
class Solution {
    void down(int i)
    {
        int new_i = i;
        if(2*i<=n&&h[2*i]>h[new_i])
            new_i = 2*i;
        if(2*i+1<=n&&h[2*i+1]>h[new_i])
            new_i = 2*i+1;
        if(new_i!=i)
        {
            swap(h[i], h[new_i]);
            down(new_i);
        }
    }
    int n;
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        n=k;
        memset(h, 0, sizeof(h));
        for(int i=0;i<k;i++)
            h[i+1]=arr[i];    
        for(int i=k/2;i>0;i--)
        {
            down(i);
        }
        for(int i=k;i<arr.size();i++)
        {
            if(arr[i]<h[1])
            {
                h[1]=arr[i];
                down(1);
            }
        }
        return vector<int>(h+1, h+k+1);
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月14日下午3:48

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[i]>= 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 条回复

mpweixin用户永久会员 2023年7月14日下午3:41

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

        PriorityQueue<Integer> queue = new PriorityQueue<>((x,y)->(y-x));

        for(int i = 0;i < arr.length;i++){
            if(queue.size() < k){
                queue.offer(arr[i]);
            }else{
                if(arr[i] < queue.peek()){//有更小的，进去
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }

        int[] result = new int[k];
        while(!queue.isEmpty()){
            result[--k] = queue.poll();
        }

        return result;
    }

0 赞同 0 条回复

Dsjh 普通 2023年7月14日下午2:46

MY

偷懒

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

0 赞同 0 条回复

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

共以下 18 个回答

MY

# 回答此问题取消回复

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

共以下 18 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复