【LeetCode】215. Kth Largest Element in an Array，基于Java和C++的解法

╰半夏微凉° 2022-08-22 14:26 23阅读 0赞

215. Kth Largest Element in an Array

Total Accepted: 57859 Total Submissions: 171725 Difficulty: Medium

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,  
Given `[3,2,1,5,6,4]` and k = 2, return 5.

Note:   
You may assume k is always valid, 1 ≤ k ≤ array's length.

# **【Section one】**分析 #

## 题意：输入一个未排序的数组，寻找第K大的数并返回。初见之下，这个题似乎比较简单，但实际操作中遇到一些有趣的问题： ##

1、采用Java，Accepted的算法，用C++实现出现了内存超限（Memory Limit Exceed）；

2、Java和C++不同的内存管理模式；

## **分析：** ##

寻找数组中第K大的数据，一个直观的思路是将数组排序，然后直接通过索引返回第K大的数据。这样做完全可以实现，但是明显做了很多无用功，由于我们只需寻找第K大的数，完全没有必要进行全排序。在所有基本的排序算法中，快速排序是一种比较优秀的算法，平均时间复杂度O(nlogn)，在排序中用到的一个重要思想：**分治**！每一次partition时，返回的都是分割后作为“**轴**”的元素的下标，其左边的元素均**小于等于**它，其右边的元素均**大于**它，因此，经过分割后，若“**轴**”元素在数组中的下标为p,则“**轴**”元素为第lengthOfArray-p大的元素；基于这种思想我们可以很快写出两种风格的程序。

# **【Section two】** #

## 基于Java语言的解法一： ##

class Solution {
        public int findKthLargest(int[] nums, int k) 
        {
        	return quickSort(0,nums.length-1,nums,k);        
        }
        
        int quickSort(int low,int high,int[] temp,int k)
        {
        	if(low>=high)return temp[low];//递归结束的约束条件
        	int point=partition(low,high,temp);//每一次分割后“轴”的下标
        	
        	if(temp.length-point==k) return temp[point];
        	else if(temp.length-point>k){
        		return quickSort(point+1,high,temp,k);
        	}
        	else{
        		return quickSort(low,point-1,temp,k);
        	}
        }
        
        public int partition(int low,int high,int[] temp)//采用分治的思想
        {
        	int cur=temp[low];
        	while(low<high)
        	{
        		while(low<high&&temp[high]>=cur)
        			--high;
        		temp[low]=temp[high];
        		while(low<high&&temp[low]<=cur)
        			++low;
        		temp[high]=temp[low];
        	}
        	temp[low]=cur;
        	return low;
        }
    }

## **基于Java的解法二：** ##

这个解法与解法一相比，都是“**分治**”的思想，但是，解法二中却消耗了大量的内存！！！！，随着递归的进行，每一层都需要分配内存用于存储子数组，且此题给定的形参为int\[\]，而根据需要我们定义的是具有动态增删功能的数组列表，在递归调用的时候，还需要复杂的转化，这也会造成时间和空间的消耗。

class Solution2 {
        public int findKthLargest(int[] nums, int k) 
        {
            List<Integer> leftarray=new ArrayList<Integer>();
            List<Integer> rightarray=new ArrayList<Integer>();//定义两个数组列表存储分割后的数组
           
            for(int i=1;i<nums.length;i++)
            {
                if(nums[i]<=nums[0])//以第一个元素为轴，将数组分成两个子数组
                {
                	leftarray.add(nums[i]);//左数组为小于等于转轴的元素
                }
                else
                {
                	rightarray.add(nums[i]);
                }
            }
            
            if(rightarray.size()>=k)//此情况下，第k大的元素必然存在于右子树组
            {
            	int[] rightRemain=new int[rightarray.size()];
            	int i=0;
            	for(Integer e:rightarray)//由于给定的方法的形参列表为int[]，这里需要转换一下
            		rightRemain[i++]=e;
            	return findKthLargest(rightRemain, k);
            }
            else if(rightarray.size()==k-1)
            {
            	return nums[0];
            }
            else
            {
            	int[] leftRemain=new int[leftarray.size()];
            	int i=0;
            	for(Integer e:leftarray)
            		leftRemain[i++]=e;
            	return findKthLargest(leftRemain, k-rightarray.size()-1);
            }
           
        }
    }

</pre><p></p><pre>

## 基于C++的解法： ##

如下为基于C++的解法，和基于Java的解法二完全相同，看上去程序更为简洁，但是，在LeetCode平台上会出现内存超限（Memory Limit Exceeded）的问题，这与C++中内存的管理模式有关：vector其中一个特点：内存空间只会增长，不会减小，援引C++ Primer：为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。设想一下，当vector添加一个元素时，为了满足连续存放这个特性，都需要重新分配空间、拷贝元素、撤销旧空间，这样性能难以接受。因此STL实现者在对vector进行内存分配时，其实际分配的容量要比当前所需的空间多一些。就是说，vector容器预留了一些额外的存储区，用于存放新添加的元素，这样就不必为每个新元素重新分配整个容器的内存空间。

同时，vector的clear()方法只能清除vector中的元素却无法释放其占用内存，一般通过vector<int>().swap(p)来释放。swap()是交换函数，使vector离开其自身的作用域，从而强制释放vector所占的内存空间。

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k)
        {
            vector<int> leftArray;
            vector<int> rightArray;
            
            for(int i=1;i<nums.size();i++)
            {
                if(nums[i]<=nums[0])
                leftArray.push_back(nums[i]);
                else
                rightArray.push_back(nums[i]);
            }
            
            if(rightArray.size()>=k)
            {
                vector<int>(leftArray).swap(leftArray);
                return findKthLargest(rightArray, k);
            }
            else if(rightArray.size()==k-1)
            {
                return nums[0];
            }
            else
            {
                int len=k-rightArray.size()-1;
                vector<int>().swap(rightArray);
                return findKthLargest(leftArray, len);
            }
        }
    };