LeetCode题目之腾讯精选练习（50题）：数组中的第K个最大元素

比眉伴天荒 2024-04-19 13:17 46阅读 0赞

# 题目 #

在未排序的数组中找到第 **k** 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例 1** :

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

**示例 2** :

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

## 算法实现 ##

public int FindKthLargest(int[] nums, int k)//第一想到的最简便的方法
    {
        
        Array.Sort(nums);
        return nums[nums.Length-k];
    }
    
    public int FindKthLargest(int[] nums, int k)//排序过程中找第k大的数
    {
        
        int max;
        for (int i = 0; i < nums.Length; i++)
        {
        
            max = i;//记录第k大的索引
            for (int j = i + 1; j < nums.Length; j++)
            {
        
                if (nums[max] < nums[j])
                    max = j;
            }
            if (i + 1 == k)//如果第k大的数正好是我们要找的数字，则直接返回不用交换
                return nums[max];
            if (max != i)//把第k大的元素交换到应有的位置
            {
        
                int temp = nums[i];
                nums[i] = nums[max];
                nums[max] = temp;
            }
        }
        return -1;
    }

## 执行结果 ##

第一个方法  
**执行结果** : 通过  
**执行用时** : 148 ms, 在所有 C\# 提交中击败了86.11%的用户  
**内存消耗** : 24.2 MB, 在所有 C\# 提交中击败了5.55%的用户  
第二个方法  
![在这里插入图片描述][2019091818091841.png]

## 小的总结 ##

总之先想到了两种常规的方法，一种直接排序再取第k大的元素，另一种只排前k个元素。看了题解后了解到了快速选择的方法，稍有些难懂，在移植过程中顺便翻译和添加一些注释，才差不多搞懂了。

## 快速选择 ##

int[] nums;
    public void swap(int a, int b)
    {
        
        int tmp = this.nums[a];
        this.nums[a] = this.nums[b];
        this.nums[b] = tmp;
    }
    
    public int partition(int left, int right, int pivot_index)//把左右之间以基准值为中心分好
    {
        
        int pivot = this.nums[pivot_index];
        // 1. 把基准值移到最后
        swap(pivot_index, right);
        int store_index = left;
    
        // 2. 把所有小于基准值的元素移到左边
        for (int i = left; i <= right; i++)
        {
        
            if (this.nums[i] < pivot)
            {
        
                swap(store_index, i);
                store_index++;
            }
        }
    
        // 3. 把基准值移到应有的位置
        swap(store_index, right);
    
        // 4. 返回基准值的下标
        return store_index;
    }
    
    public int quickselect(int left, int right, int k_smallest)
    {
        
        /*
        返回左右之间第k小的元素
        */
    
        if (left == right) // 如果左右相等，即只有一个元素
            return this.nums[left];  // 返回那个元素
    
        // 选择一个随机的基准值的下标
        Random random_num = new Random();
        int pivot_index = left + random_num.Next(right - left);
    
        pivot_index = partition(left, right, pivot_index);
    
        // 基准值是第(N - k)小的元素，即第k大的元素
        if (k_smallest == pivot_index)
            return this.nums[k_smallest];
        // 去左（小于基准值的）区间
        else if (k_smallest < pivot_index)
            return quickselect(left, pivot_index - 1, k_smallest);
        // 去右（大于基准值的）区间
        return quickselect(pivot_index + 1, right, k_smallest);
    }
    
    public int FindKthLargest(int[] nums, int k)
    {
        
        this.nums = nums;
        int size = nums.Length;
        // 第k大即第(N - k)小的元素
        return quickselect(0, size - 1, size - k);
    }

![在这里插入图片描述][20190918192333450.png]

[2019091818091841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c577f4b380c047998ddfaf0047c27c5d.png
[20190918192333450.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/94cabf323d674827a0adf7c9a930b218.png