数组中的第K个最大元素

前言

运用Scala的语法实现数组中的第K个最大元素

一、数组中的第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

二、实现步骤

代码如下（示例）：

利用 partition分区函数，初始将最后一个元素arr[len-1]作为 pivot（分区点），
将数组中小于 pivot 的点都放置到其左边，将大于pivot的点都放置在其右边，最终 partition 函数返回 pivot 的下标 i
1当 partition 函数返回的下标 i=len-k，则 arr[i] 就是我们要求的第K大元素
2、当 partition 函数返回的下标 i<len-k，那么说明第K大元素在下标 i 的右边，我们继续分区在 arr[i+1, len-1] 区间内查找：partition(arr, i+1, len-1)
3、当 partition 函数返回的下标 i>len-k，那么说明第K大元素在下标 i 的左边，我们继续分区在 arr[0, i-1] 区间内查找：partition(arr, 0, i-1)

def findKthLargest(nums: Array[Int], k: Int): Int = {val len=nums.lengthval resIndex=len-k//结果元素的索引//pivot点刚好是第K大元素，那么它的左边一定有 K-1 个不小于它的元素，它的下标应该是 len-kvar left=0var right=len-1while(true){val ind=partition(nums,left,right)if (ind==resIndex)return nums(ind)else if(ind>resIndex)//说明第K大元素在下标 i 的左边，我们继续分区在 arr[0, i-1] 区间内查找right=ind-1else //说明第K大元素在下标 i 的右边，我们继续分区在 arr[i+1, len-1] 区间内查找left=ind+1}Int.MinValue
}

分区函数，将 arr[high] 作为 pivot 分区点
i、j 两个指针，i 作为标记“已处理区间”和“未处理区间”的分界点，也即 i 左边的（low~i-1）都是“已处理区”。
j 指针遍历数组，当 arr[j] 小于 pivot 时，就把 arr[j] 放到“已处理区间”的尾部，也即是 arr[i] 所在位置
因此 swap(arr, i, j) 然后 i 指针后移，i++
直到 j 遍历到数组末尾 arr[high]，将 arr[i] 和 arr[high]（pivot点） 进行交换，返回下标 i，就是分区点的下标。

def partition(arr:Array[Int],left:Int,right:Int): Int ={if (right > left) {//当数组近乎有序时//在下标 low 和 high 之间随机选择，然后和下标 high 元素进行交换val random = left +Random.nextInt(right-left);swap(arr, right, random);}var i=leftval pivot=arr(right)for(j <- left until right if arr(j)<pivot) {swap(arr,i,j)i+=1}swap(arr,i,right)i
}def swap(arr:Array[Int],i:Int,j:Int): Unit ={val tmp=arr(i)arr(i)=arr(j)arr(j)=tmp
}