Kth Largest Element in an Array解题报告-白红宇的个人博客

发布日期：2022-02-25 00:55:19 浏览次数：48 分类：技术文章

本文共 2776 字，大约阅读时间需要 9 分钟。

这是道中等题，不难，一般都能Accepted,关键是看能不能在时间复杂度上面做优化。

首先我能想到的是用选择排序的思想，由大到小排序，一直到排到第K大个就停止并返回，这样对于n个元素的数组，平均时间复杂度为

O(n2) $O(n^2)$ ,下面是C++代码的实现:

class Solution {public:    int findKthLargest(vector
   
    & nums, int k) {        int n = nums.size();        int index,tmp;        for(int i=0; i < k; i++){            index = i;            tmp = nums[i];            for(int j=i+1;j < n; j++){                if(nums[index] < nums[j]){                    index = j;                }            }            nums[i] = nums[index];            nums[index] = tmp;        }        return nums[k-1];    }};

提交后的情况

运行时间176ms,从分布图上看出这是特别慢的，于是做了小小的优化，即比较k 与数组的中间位置n/2,k在n/2左边时就采用上面的算法，在右边时就将问题转化为寻找第n - k + 1个小的元素，代码如下:

class Solution {
   public:    int findKthLargest(vector
   
    & nums, int k) {        int n = nums.size();        int mid = n/2;        int index,tmp;       if(k <= mid){            for(int i=0; i < k; i++){            index = i;            tmp = nums[i];            for(int j=i+1;j < n; j++){                if(nums[index] < nums[j]){                    index = j;                }            }            nums[i] = nums[index];            nums[index] = tmp;        }        return nums[k-1];       }    else{        k = n - k + 1;        for(int i=0; i < k; i++){            index = i;            tmp = nums[i];            for(int j=i+1;j < n; j++){                if(nums[index] > nums[j]){                    index = j;                }            }            nums[i] = nums[index];            nums[index] = tmp;        }        return nums[k-1];    }    }};

这里写图片描述

用时49ms,快了一些，但是时间复杂度仍然是

O(n2) $O(n^2)$ ，后来在讨论区看到了quickSelect 算法，并参考了维基百科上的，并用C++实现，代码如下:

class Solution {public:    int findKthLargest(vector
   
    & nums, int k) {        int left = 0;        int right = nums.size() - 1;        srand((unsigned)(time(NULL)));        while(1){            if(left == right){                return nums[left];            }           int pivotIndex = rand() % (right - left + 1) + left;           pivotIndex = partition(nums,left,right,pivotIndex);           if(pivotIndex == k - 1){               return nums[k-1];           }           else if(pivotIndex < k - 1){               left = pivotIndex + 1;           }           else{               right = pivotIndex - 1;           }        }    }private:    int partition(vector
    
     & nums,int left,int right,int pivotIndex){        int pivotValue = nums[pivotIndex];        int storeIndex = left;        swap(nums[right],nums[pivotIndex]);        for(int i = left; i < right; i++){            if(nums[i] > pivotValue){                swap(nums[i],nums[storeIndex]);                storeIndex++;            }        }        swap(nums[right],nums[storeIndex]);        return storeIndex;    }};

这里写图片描述

9ms，优化效果不错。

这次解题的最大收获是学会了quick select 算法

转载地址：https://blog.csdn.net/qq_30306087/article/details/77925379 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：这是标题

下一篇：Number of Longest Increasing Subsequence 解题报告

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章