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

小肸永久会员 2023年9月16日下午11:12

class Solution {
    //在数组有序的情况下，并且k=arr.length，此时时间复杂度最坏为O(n^2)（n次递归调用，每一个递归调用的时间复杂度为O(N)）
    //空间复杂度最坏为O(n)(n次递归调用，每一次递归调用空间占用为常量级别)。
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSortTopK(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i ++) {
            res[i] = arr[i];
        }
        return res;
    }
    private void quickSortTopK(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int i = left, j = right;
        int baseVal = arr[left];//选取最左边的元素作为基准值
        while (i < j) {
            while (i < j && arr[j] >= baseVal) {
                j --;
            }
            while (i < j && arr[i] <= baseVal) {
                i ++;
            }
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        arr[left] = arr[i];//赋值下一次递归的基准值
        arr[i] = baseVal;//找到了基准值升序排列的位置
        if (i == k) {
            return;
        } else if (i > k) {
            quickSortTopK(arr, left, i - 1, k);
        } else {
            quickSortTopK(arr, i + 1, right, k);
        }
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月9日上午12:24

先排序，然后输出最小的k个

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 start, int end){
        if(start < end){
            int low = start, high = end;
            int pivot = arr[start];
            while(low < high){
                while(low < high && arr[high] >= pivot){
                    high--;
                }
                arr[low] = arr[high];
                while(low < high && arr[low] <= pivot){
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = pivot;
            quickSort(arr, start, low);
            quickSort(arr, low + 1, end);
        }
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月8日下午10:31

快排

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

        return quickFind(arr, 0, arr.length - 1, k);
    }

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

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

        int i = left;
        int j = right;

        while (i < j ) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            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 条回复

sincere 普通 2023年9月8日下午2:41

思路：1、直接用库函数排序后取前k个；2、快速排序是基准值左边都小于它右边都大于它，假设基准值刚好是第k+1个元素，那么此时遍历完的左侧就是需要的k个数。所以可以设计基于快速排序的数组划分；
复杂度：时间复杂度O(n)，空间复杂度O(1)

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

    public int[] quickFind(int[] arr, int low, int high, int k) {
        int i = low, j = high;
        int povit = arr[low];
        while (i < j) {
            while ((i < j) && povit <= arr[j]) {
                j--;
            }
            while ((i < j) && povit >= arr[i]) {
                i++;
            }
            if (i != j) {
                exchange(arr, i, j);
            }
        }
        exchange(arr, low, i);
        if (i > k) {
            return quickFind(arr, low, i - 1, k);
        }
        if (i < k) {
            return quickFind(arr, i + 1, high, k);
        }
        return Arrays.copyOf(arr, k);
    }

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

0 赞同 0 条回复

行动派小彩笔普通 2023年9月6日下午3:36

// 冒泡排序 时间复杂度O(kn),空间复杂度O(k)
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.size() <= k) return arr;
        for(int i=0;i<k;++i)
        {
            for(int j=arr.size()-1;j>i;--j)
            {
                if(arr[j]<arr[j-1]) swap(arr[j],arr[j-1]);
            }
        }
        vector<int> res(k,-1);
        for(int i=0;i<k;++i)
        {
            res[i]=arr[i];
        }
        return res;
    }
};
// 快排思想进行划分
class Solution {
public:
    int partition(vector<int>& arr,int l,int r)
    {
        int j=l;
        for(int i=l;i<r;++i)
        {
            if(arr[i]<arr[r])
            {
                swap(arr[i],arr[j]);
                j++;
            }
        }
        swap(arr[j],arr[r]);
        return j;
    }
    void quickSort(vector<int>& arr,int l,int r,int k)
    {
        if(l>=r) return;
        int mid = partition(arr,l,r);
        if(mid+1 == k) return;
        else if(mid+1>k)
        {
            quickSort(arr,l,mid-1,k);
        }
        else
        {
            quickSort(arr,mid+1,r,k);
        }
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.size()<=k) return arr;
        quickSort(arr,0,arr.size()-1,k);
        vector<int> res(k,-1);
        for(auto s:arr)
        {
            cout<<s<<" ";
        }
        for(int i=0;i<k;++i)
        {
            res[i]=arr[i];
        }
        return res;
    }
};

0 赞同 0 条回复

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

共以下 5 个回答

# 回答此问题取消回复

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

共以下 5 个回答

# 回答此问题 取消回复

# 回答此问题取消回复