算法思想一：冒泡局部排序

解题思路：

只排序前K个数

1、主要利用冒泡排序算法对数组进行排序

2、从排序后的数组中直接获取第K大的数值

代码展示：

Python版本 

class Solution:
    def findKth(self, a, n, K):
        # write code here
        # 冒泡排序  只需要对top K个数进行排序
        for i in range(K):
            for j in range(n-i-1):
                if a[j] > a[j+1]:
                    # 交换两个数字
                    tmp = a[j]
                    a[j] = a[j+1]
                    a[j+1] = tmp
        return a[n-K]

复杂度分析

时间复杂度：N表示数组长度，最差情况K趋近与n时复杂度为

空间复杂度：仅使用常数级空间变量

算法思想二：快排+二分

解题思路：

  • 采用快速排序，每次以当前表中第一个元素为轴来对表进行划分，将表中比枢轴大的元素向左移，比表中小的元素向右移，使得下一趟partition操作后，表中的元素备枢轴一份为二。每次partition可以确定一个第大元素，如果，则是第K大元素
  • 找到第K大的数，也就是找到数组排序后位于n-K位置的数，利用快排的partation函数，可以得到一个数的位置index。如果，则返回，如果小于index 则在做边区间去找，如果大于则在右半区间找。

代码展示：

JAVA版本 

import java.util.*;
public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        // 快速排序
        return quickSort(a, 0, a.length - 1, K);
    }
    private int quickSort(int[] arr, int left, int right, int k){
        int p = partition(arr, left, right);
        // 改进后，很特殊的是，p是全局下标，只要p对上topK坐标就可以返回
        if (p == arr.length - k) {
            return arr[p];
        }else if (p < arr.length - k) {
            // 如果基准在左边，这在右边找
            return quickSort(arr, p + 1, right,k);
        }else {
            return quickSort(arr, left, p - 1,k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        // 可优化成随机，或中位数
        int key = arr[left];
        while (left < right) {
            while (left = key) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
}

复杂度分析

时间复杂度：N表示数组长度，查找时间，随机选择时间

空间复杂度：递归调用栈空间

算法思想三：小根堆

解题思路：

通过构造小根堆进行数组排序，在排序过程中查找第K大的点
算法流程：

1、遍历数组

2、如果堆的大小小于K，则将数组元素入堆，反之，移除堆的根，并将当前元素入堆

3、遍历结束返回 堆的首元素

代码展示：

JAVA版本 

import java.util.*;
public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        //小根堆
        PriorityQueue pq = new PriorityQueue() ;
        for(int i = 0 ; i < n ; i++)
        {
            if(pq.size() < K)
            {
                pq.add(a[i]) ;
            }else if(a[i] > pq.peek()){
                pq.remove() ;
                pq.add(a[i]) ;
            }
        }
        return pq.peek();
    }
}

复杂度分析

时间复杂度：N表示数组长度，构建堆时间，操作堆时间

空间复杂度：堆空间