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

0x00 问题简述

给定一个数组，找出该数组中第n大的元素的值。其中,1<=n<=length。例如，给定一个数组A={2，3，6，5，7，9，8，1，4}，当n=1时，返回9。

0x01 先排序

我拿到这个问题的地中思路就是先排序，然后通过位置索引相应的第n大的元素。我使用的是O(nlog(n))级别的排序算法，所以这种方法的时间复杂度应该也是O(nlog(n))级别的。

那这个问题有没更好的解决办法呢？是有的，我们参考快速排序的思想，可以做到O(n)级别。在此之前我们先回顾一下快速排序。

0x02 快速排序

我这里只是简述以下快速排序的思路。快速排序中最重要的就是partition操作，就是将我们最左边的数k移动到最佳位置（k左边的数都小于k，k右边的数都大于k）

我们通过以下这个例子回顾以下具体操作方式

具体的partition操作代码

template
   
    int __partition(T arr[], int l, int r){
   	std::swap(arr[l], arr[rand() % (r - l + 1) + l]);	int j = l;	for (int i = l + 1; i <= r; ++i)	{
   		if (arr[i] < arr[l])		{
   			std::swap(arr[++j], arr[i]);		}	}	std::swap(arr[l], arr[j]);	return j;}
   

上面代码是最基础的操作。

0x03 O(n)级别的处理

我们通过快速排序中的思想，可以很快地解决这个问题

template
   
    int __partition(T arr[], int l, int r){
       std::swap(arr[l], arr[rand() % (r - l + 1) + l]);    int j = l;    for (int i = l + 1; i <= r; ++i)    {
           if (arr[i] < arr[l])        {
               std::swap(arr[i], arr[++j]);        }    }    std::swap(arr[l], arr[j]);    return j;}template
    
     int __selection(T arr[], const int& l, const int& r, const int& k){
       if (l == r) return arr[l];    int p = __partition(arr, l, r);    if (k == p) return arr[p];    else if (k < p) return __selection(arr, l, p - 1, k);    else return __selection(arr, p + 1, r, k);}template
     
      int selection(T arr[], const int& n, const int& k){
       assert(k >= 0 && k < n);    srand(time(NULL));    return __selection(arr, 0, n - 1, k);}
     
    
   

我们回顾上面的做法，不难发现，我们每次对问题的规模缩小一半，算法复杂度为

n + n/2 + n/4 + ... + 1 = 2n，即为O(2n)。

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