题目

:::info

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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


来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ::: image.png

代码

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         int length = nums.length;       //获取数组长度
  4.         bubbleSort(nums);      //对数组做升序排序
  5.         return nums[length - k];
  6.     }
  8.     //冒泡排序
  9.     public static void bubbleSort(int[] arr){
  10.         for (int i = 0; i < arr.length - 1; i++) {
  11.             for (int j = 0; j < arr.length - i - 1; j++) {
  12.                 int tmp = 0;
  13.                 if (arr[j] > arr[j+1]){
  14.                     tmp = arr[j+1];
  15.                     arr[j+1] = arr[j];
  16.                     arr[j] = tmp;
  17.                 }
  18.             }
  19.         }
  20.     }
  22.     //优化冒泡排序
  23.     public static void optimalBubbleSort(int[] arr){
  24.         int lastExchangeIndex = 0;       //记录最后一次交换的位置
  25.         int sortBorder = arr.length - 1;        //无序数列的边界
  26.         for (int i = 0; i < arr.length - 1; i++) {
  27.             boolean isSorted = true;        //有序标记，当一轮循环元素无交换时为true
  28.             for (int j = 0; j < sortBorder; j++) {
  29.                 int tmp = 0;
  30.                 if (arr[j] > arr[j+1]){
  31.                     tmp = arr[j];
  32.                     arr[j] = arr[j+1];
  33.                     arr[j+1] = tmp;
  34.                     isSorted = false;        //元素位置发生改变
  35.                     lastExchangeIndex = j;         //记录最后一次交换的位置
  36.                 }
  37.             }
  38.             sortBorder = lastExchangeIndex;
  39.             if (isSorted)break;                //当元素位置不发生变化时，说明此时已经有序
  40.         }
  41.     }
  42. }