leetcode刷题之第215题：数组中的第K个最大元素（多种解法）

题目描述

在未排序的数组中找到第 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
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

暴力破解法思路

这题解法很多，基本上都是排序后取第K大的树，理论上说采用二叉排序树储存方法是一种很好的解法，但是因为手里有归并排序函数模板所以直接用了归并排序。

代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()==1)
        return nums[0];

        vector<int> result;
        result.resize(nums.size());
        MergeSort(nums,0,nums.size()-1,result);
        return result[nums.size()-k];

    }
    void MergeSort(vector<int> &a, int left, int right, vector<int> &b)
{
	int t;
	if (left < right)
	{
		int mid = (left + right) / 2;
		MergeSort(a, left, mid, b);
		MergeSort(a, mid + 1, right, b);
		int t = 0;
		int i = left;
		int j = mid + 1;
		while (i <= mid && j <= right)
		{
			if(a[i]<a[j])
			{
				b[t++] = a[i++];
			}
			else
			{
				b[t++] = a[j++];
			}
		}
		while (i<=mid)
		{
			b[t++] = a[i++];
		}
		while (j <= right)
		{
			b[t++] = a[j++];
		}
		t = 0;
		while (left <= right)
		{
			a[left++] = b[t++];
		}
	}

}
};

在学了有关优先队列（堆）的知识后学到一个解决这个问题有效的算法，并且占用的内存也小很多

巧妙简单的解法思路

第一步：将K个元素读入一个数组并将其排序。
第二步：处理元素时，先将该元素与数组中的第K的元素进行比较，如果该元素大，那么将第K个元素删除，从而将这个新元素放在其余K-1个元素间的正确的位置上。
第三步：输出第K个位置上的元素

时间复杂度分析

该方法的运行时间为O（N*K），当K相较于数组元素N很小时这无疑是个很好的算法。如果K=N/2，那么这种算法达到了O（N^2)。下面给出两个算法，在K=N/2的极端情况下，这两种算法都以O（NlogN）时间运行，这是明显的改进。

堆的解法

为了简单起见，假设我们只考虑找出第K个最小元素。该算法很简单。先将N个元素读入一个数组，然后堆数组应用buildHeap算法（该算法为堆的基础算法，在数据结构与算法分类中对此会有详解）。最后，执行K次deletMin操作。最后从该堆提取的元素就是正确答案。显然，只要改变堆序性质，就可以解决原始的问题：找出第K个最大的元素。

另外一个思路是，用堆实现巧妙简单解法。通过调用buildHeap将前k个元素以总时间O（k）放入堆中。处理其余的每个元素的时间为O（1），还要加上O（logk）时间，用来检测元素是否放入S，并在需要时删除Sk并插入新元素。