首页 Algorithm

# 题目描述

在数组中找到第 k 大的元素。

给出数组 [9,3,2,4,8] ，第三大的元素是 4

给出数组 [1,2,3,4,5] ，第一大的元素是 5 ，第二大的元素是 4 ，第三大的元素是 3 ，以此类推

要求时间复杂度为 O (n)，空间复杂度为 O (1)

# 问题分析

如果不考虑时间复杂度和空间复杂度，这道题目有很多种方法，利用一种排序算法将数组倒叙排序，第 k 个数就是第 k 大元素。

题目的重点在于返回第 K 大元素，而其他元素并不关心。如果要返回第 K 大元素，必然要先找到比 K 大的 k-1 个数，这 k-1 个数的顺序也并不用关心。如果我们使用冒泡、选择等常规排序，需要从最大的开始找起，那么时间复杂度就是 O (n * k)，当 k 较大时，时间复杂度太高。

快速排序算法的特点就在于经过一次遍历，可以分别找到比某个元素小的数和大的数，如果比这个元素大的数的个数恰好是 k-1，那么这个数就正是我们要找的数。假如经过一次遍历之后，元素 A 左边的元素均大于 A，右边的元素均小于 A，A 的数组下标是 index，若 index+1=k，那么 A 就是第 k 大元素；若 index+1>k，那么第 k 大元素就在数组的 0～index-1 中，此时问题就变为了在数组的 0～index-1 中寻找第 k 大元素，继续循环遍历操作直到存在某个 index 使 index+1=k 为止；若 index+1<k，那么第 k 大元素就在数组的 index+1～length-1 中，循环遍历子数组知道找到某个 index 使 index+1=k 即可。时间复杂度 = O (n + n/2 + n/4 + ... + 1)<O (2n)=O (n)。

# 代码实现

public int kthLargestElement(int n, int[] nums) {
    int low = 0;
    int high = nums.length - 1;
    while (low <= high) {
        int index = low - 1;
        for (int i = low; i < high; i++) {
            if (nums[i] > nums[high]) {
                swap(nums, i, ++index);
            }
        }
        swap(nums, high, ++index);
        if (index + 1 == n) {
            return nums[index];
        } else if (index + 1 > n) {
            high = index - 1;
        } else {
            low = index + 1;
        }
    }
    return -1;
}
private void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}