阵列Leetcode解决方案中的第K个最大元素  


难度级别 中等
经常问 土砖 亚马逊 Apple ByteDance 易趣 Expedia的 Facebook 谷歌 LinkedIn 微软 神谕 Salesforce的 Spotify 沃尔玛实验室
算法 排列 编码 分而治之 访谈 面试准备 力码 力码解决方案

在此问题中,我们必须在 未分类 排列。 请注意,数组可以有重复项。 因此,我们必须找到 th 按排序顺序排列的最大元素,而不是唯一的第K个最大元素。

使用案列  

A = {4 , 2 , 5 , 3 , 1}
K = 2
4
A = {7 , 2 , 6 , 4 , 3 , 5}
K = 4
4

方法(排序数组)  

这种方法很简单。 对整个数组进行排序。 现在,您可以分辨出数组中任何最大的元素。 但是,足以让我们找到 th 最大的元素。 这就是为什么我们可以提出一种更好的方法的原因。

算法

  1. 对数组排序
  2. 从数组后面访问第K个最大元素
  3. 打印答案

查找未排序数组中第K个最大元素的算法的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;



int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    sort(a.begin() , a.end());
    return a[n - k];
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java程序

import java.util.Arrays;


class Kth_largest
{
    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        Arrays.sort(a);
        return a[n - k];
    }

    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

在未排序数组中找到第K个最大元素的复杂度分析

时间复杂度

O(NlogN),因为我们需要对数组进行排序。 N =数组的大小

参见
路径穿越Leetcode解决方案

空间复杂度

O(1), 因为我们使用恒定的空间。 备注: 种类() 功能可以使用 上) 记忆。 但这并非总是如此。

方法(快速选择)  

正如我们在之前的方法中讨论的那样,我们只需要找到 th 数组中的最大元素。 以一种更简单的方式,我们需要数组中第(n – k + 1)个最小的元素。 说到排序,我们可以想到 快速排序,也有类似的方法。 在快速排序中,选择一个 枢纽,我们确保它在分区之后到达数组中的正确索引。

如果,我们进行了类似的分区,直到(n – k)索引得到正确的值。 这就是我们将要采用的方法:

未排序数组Leetcode Solutions中的第K个最大元素

选择一些随机枢轴并对其周围的数组进行分区。 如果它达到索引,我们期望(n – k)。 那么,这是第K个最大元素。 否则,我们知道所需索引位于其左侧或右侧。 然后,我们可以致电 划分() 在相应的功能 子阵列 查找所需的索引及其值。

但是,上述方法是否肯定比 排序 一? 我们知道,在这种情况下,当我们选择最小/最大元素作为关键点时,就会发生快速排序的最坏情况,

T(N)= T(N – 1)+ O(1)

子问题与问题几乎相同,从而导致O(N * N)时间复杂性。 同样,我们的分区功能可以进行此类调用。 为了解决这个问题,我们将确保我们选择一个 随机 在分区的每个点旋转。

参见
范围最大奇数的XOR查询

算法

  1. 创建一个 quickSelect() 返回第(N – K)个“最少“ 元素
  2. 创建一个 划分() 辅助函数,它将返回任何正确的索引 随机 选择的枢轴
  3. 现在,直到我们到达 划分() 返回等于'的索引K“:
    • 在一个分区上调用partition() 随机 枢纽
    • 如果返回的数据透视表索引与 K
      • 返回枢轴元素
    • 否则,如果返回的枢轴索引小于 K
      • 调用partition() 子阵列 枢轴索引的
    • 否则,如果返回的枢轴索引大于 K
      • 调用partition() 左子数组 枢轴索引的
  4. 现在, quickSelect() 返回了第(N – K)个索引,打印结果

查找未排序数组中第K个最大元素的算法的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;



int partition(int &l , int &r , vector <int> &a)
{
    int rnd = (rand() % (r - l + 1)) + l;
    swap(a[rnd] , a[r]);

    int idx = l;
    for(int i = l ; i < r ; i++)
    {
        if(a[i] < a[r])
        {
            swap(a[i] , a[idx]);
            idx++;
        }
    }

    swap(a[idx] , a[r]);
    return idx;
}

int quickSelect(int l , int r , int k , vector <int> &a)
{
    while(l <= r)
    {
        int pivotIdx = partition(l , r , a);
        if(pivotIdx == k)
            return a[pivotIdx];
        if(pivotIdx < k)
            l = pivotIdx + 1;
        else
            r = pivotIdx - 1;
    }
    return -1;
}


int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    return quickSelect(0 , n - 1 , n - k , a);
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java程序

import java.util.Random;


class Kth_largest
{
    static void swap(int x , int y , int [] a)
    {
        int temp = a[y];
        a[y] = a[x];
        a[x] = temp;
        return;
    }

    static int partition(int l , int r , int [] a)
    {
        Random rndObject = new Random();
        int rnd = rndObject.nextInt(r - l + 1) + l , idx = l;
        swap(rnd , r , a);
        for(int i = l ; i < r ; i++)
        {
            if(a[i] < a[r])
            {
                swap(i , idx , a);
                idx++;
            }
        }
        swap(idx , r , a);
        return idx;
    }


    static int quickSelect(int l , int r , int k , int [] a)
    {
        while(l <= r)
        {
            int pivotIdx = partition(l , r , a);
            if(pivotIdx == k)
                return a[pivotIdx];
            if(pivotIdx < k)
                l = pivotIdx + 1;
            else
                r = pivotIdx - 1;
        }
        return -1;
    }

    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        return quickSelect(0 , n - 1 , n - k , a);
    }


    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

在未排序数组中找到第K个最大元素的复杂度分析

时间复杂度

递归关系可以表示为N =数组的大小):

参见
搜寻器日志文件夹Leetcode解决方案

T(N)= T(N / 2)+ O(N – 1)

因为我们期望随机选择的枢轴将数组分成两半。 基于此,可以将复杂度粗略估算为 T(N)= 2N – logN =〜O(N)。

因此,该算法是线性的。 然而,在最坏的情况下,当选择了随机枢轴都是最大/最小的数组中,时间复杂度变 O(N * N)。 但是在大型阵列中,发生这种情况的可能性很小。

空间复杂度

O(1), 因为只使用恒定的空间。