leetcode 215. Kth Largest Element in an Array 堆排序的简单应用 + 快速排序

Dear 丶 2022-06-08 10:12 129阅读 0赞

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,  
Given \[3,2,1,5,6,4\] and k = 2, return 5.

这道题就是一道简单的堆排序的问题。

注意学习堆排序。

代码如下：

/*
     * 考查的是堆排序
     * 其实最简单的方法是快排，然后找到k大值即可
     * */
    public class Solution 
    {
        public static void main(String[] args)
        {
            int[] a = { 3, 2, 1, 5, 6, 4 };
            Solution solution=new Solution();
            System.out.println(solution.findKthLargest(a, 2));
        }
    
        public int findKthLargest(int[] nums, int k) 
        {
            if(nums==null || k<=0)
                return 1;
            int[] heap = new int[nums.length];
    
            for(int i=0;i<nums.length;i++)
                shiftUp(nums[i],i,heap);
    
            //调整k-1次，然后heap[0]保留的就是k大值
            int lastIndex=nums.length;
            for(int i=0;i<k-1;i++)
            {
                swap(heap, 0, lastIndex-1);
                shiftDown(heap,lastIndex-1);
                lastIndex--;
            }
            return heap[0];
        }
    
        /*
         * len 表示heap的length
         * 删除堆顶元素后，向下调整
         * */
        private void shiftDown(int[] heap, int len) 
        {
            int parent=0;
            while(parent<len)
            {
                int child=2*parent+1;   
                //我们是要选出最大的child和parent做交换
                if(child+1<len && heap[child]<heap[child+1])
                    child+=1;
                //注意这里的child的范围控制
                if(child<len && heap[child]>heap[parent])
                {
                    swap(heap, child, parent);
                    parent=child;
                }
                else
                    break;  
            }
        }
    
        /*
         * 插入到堆中，要想想调整
         * */
        private void shiftUp(int num, int index, int[] heap)
        {
            heap[index]=num;
            int p=index;
            while(p>0)
            {
                int parent=(p-1)/2;
                if(heap[parent]<heap[p])
                    swap(heap,p,parent);
                p=parent;
            }
        }
    
        public void swap(int[] heap, int a, int b) 
        {
            int tmp=heap[a];
            heap[a]=heap[b];
            heap[b]=tmp;
        }
    }

下面是C++的做法，这是一个堆排序的简单应用，十分基础的问题

本题题意是考察快速排序，第k大可以换位第k小的数字，这样直接求解即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
    
        int part(vector<int>& a, int beg, int end)
        {
            int key = a[beg];
            int i = beg, j = end;
            while (i < j)
            {
                while (i<j && a[j]>key)
                    j--;
                a[i] = a[j];
                while (i<j && a[i]<key)
                    i++;
                a[j] = a[i];
            }
            a[i] = key;
            return i;
        }
    
        void qsort(vector<int>& a, int beg, int end,int k)
        {
            if (beg < end)
            {
                int mid = part(a, beg, end);
                int len = mid - beg + 1;
                if (len == k)
                    return;
                else if (len > k)
                    qsort(a, beg, mid - 1,k);
                else
                    qsort(a, mid + 1, end,k-len);
            }
        }
    
        int findKthLargest(vector<int>& a, int k)
        {
            if (k <= 0 || k > a.size())
                return 0;
            k = a.size() + 1 - k;
            qsort(a, 0, a.size() - 1,k);
            return a[k - 1];
        }
    };