Likou 215 questions, the Kth largest element in an array

力扣215题,数组中的第K个最大元素

题目描述

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素.

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素.

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题.

输入输出样例

输入: [3,2,1,5,6,4], k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

解法一,暴力解法

//Solution 1 does not consider the time complexity
//时间复杂度为O(nlogn)
    int findKthLargest(vector<int>&nums,int k)
    {
      
        if(nums.empty())
        {
    
            return NULL;
        }

        sort(nums.begin(),nums.end());

        int length=nums.size();
        return nums[length-k];
    }

时复 O(NlogN) 空复 O(logN)

解法二,使用快速排序,先排序再取值（三路排序）

//Done using the idea of ​​quicksort

    int findKthLargest2(vector<int>&nums,int k)
    {
    
        quickSorts2(nums,0,nums.size()-1);

        return nums[nums.size()-k];        
    }

    // void quickSort(vector<int>&nums,int left,int right)
    // {
    
    // if(left>=right)
    // {
    
    // return;
    // }

    // int pivotIndex=partition(nums,left,right);

    // quickSort(nums,left,pivotIndex-1);
    // quickSort(nums,pivotIndex+1,right);
    // }

    //划分在顺序数组和逆序数组上表现很差的
    //解决方法随机选择切分元素

    void randomPartiton(vector<int>&nums,int left,int right)
    {
    
        int i=left+rand()%(right-left+1);
        swap(nums,i,left);
    }

    void quickSorts2(vector<int>&nums,int left,int right)
    {
       
        //当左边大于右边,那么就可以跳出循环
        if(left>=right)
        {
    
            return;
        }

        randomPartiton(nums,left,right);
        int pivot=nums[left];

        // 将pivot后面的元素划分成三个区间
        //all in nums[left+1,lt)<pivot;
        //all in nums[lt,i)=pivot;
        //all in nums(gt,right]>pivot;

        //设定边界的初始条件
        int lt=left+1;//lt=less than
        int gt=right; //gt= greater than
        int i=left+1;

        while(i<=gt)
        {
    
            //当元素小于当前划分的值时
            if(nums[i]<pivot)
            {
    
                //交换到等于pivot区间的第一个位置
                swap(nums,i,lt);
                lt++;
                i++;
            }
            else if(nums[i]==pivot)
            {
    
                //划分在第二个区间里
                i++;
            }
            else{
    
                 //划分到数组的末尾
                 swap(nums,i,gt);
                 gt--;   
            }
        }
        //交换 pivot
        swap(nums,left,lt-1);



        //继续递归进行排序
        quickSorts2(nums,left,lt-2);
        quickSorts2(nums,gt+1,right);
    }

    void swap(vector<int>&nums,int index1,int index2)
    {
    
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }

解法三,Algorithm for subtraction using quicksort（双端）

void swap(vector<int>&nums,int index1,int index2)
    {
    
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }


    //借用快速排序的思想,Use mitigation methods
    //According to the titlek个元素,That means to findpivot恰好等于length-k;

    int findKthLargest3(vector<int>&nums,int k)
    {
    
        //初始化参数
        int length=nums.size();
        int left=0;
        int right=nums.size()-1;
        int target=length-k;

        //Use the idea of ​​​​two-way quick row to find the center

        while(left<=right)
        {
    
            int pivotIndex=partitionDouble(nums,left,right);
            if(pivotIndex==target)
            {
    
                return nums[pivotIndex];
            }
            else if(pivotIndex<target)
            {
    
                 left=pivotIndex+1;
            }
            else{
    
                
                right=pivotIndex-1;
            }
        }
    }

     int partitionDouble(vector<int>&nums,int left,int right)
     {
    
        //随机选取
        randomPartiton(nums,left,right);
        int pivot=nums[left];

        //Set two intervals
        //[left+1,le)<=pivot;
        //(ge,right]>=pivot;

        //Initialize both ranges so that the original is empty
        int le=left+1;
        int ge=right;

        while(true)
        {
    
            //le遇到比pivot大的停下来
            while(le<=ge&&nums[le]<pivot)
            {
    
                le++;
            }

            //ge遇到比pivotSmall break to come
            while(le<=ge&&nums[ge]>pivot)
            {
    
                ge--;
            }

            if(le>=ge)
            {
    
                break;
            }

            //交换二者的值
            swap(nums,le,ge);
            le++;
            ge--;
        }

        //交换pivot
        swap(nums,left,ge);
        return ge;
     }

时复：O(n)

空复：O(logn)

解法四,Borrowed from heap sort（最大堆)

 //Use heap sort
    int findKthLargest4(vector<int>&nums,int k)
    {
    
        int heapSize=nums.size();
        //建立堆
        buildMaxHeap(nums,heapSize);

        //Cull from the max heap,and gradually rebuild
        for(int i=nums.size()-1;i>=nums.size()-k+1;i--)
        {
    
            swap(nums,0,i);
            heapSize--;
            maxHeapiy(nums,0,heapSize);
        }
        return nums[0];
    }

    void buildMaxHeap(vector<int>&nums,int heapSize)
    {
    
        for(int i=heapSize/2;i>=0;i--)
        {
    
            maxHeapiy(nums,i,heapSize);   
        }
    }

    void maxHeapiy(vector<int>&nums,int i,int heapSize)
    {
    
        int left=i*2+1;
        int right=i*2+2;
        int largest=i;

        if(left<heapSize&&nums[left]>nums[largest])
        {
    
            largest=left;
        }

        if(right<heapSize&&nums[right]>nums[largest])
        {
    
            largest=right;
        }

        if(largest!=i)
        {
    
            swap(nums,i,largest);
            maxHeapiy(nums,largest,heapSize);

        }
    }

时复O(nlogn)

空复O(logn)