leetcode_215. 数组中的第K个最大元素

One minute read
LeetCode
面试 • 算法 • 数据结构

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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路

简单无脑：排序后取第K大

优化：使用快排，中途找到第K的时候就可以提前退出了

解答

func findKthLargest(nums []int, k int) int {
    return quickSort(nums, 0, len(nums)-1, k)
}

func quickSort(nums []int, low, high, k int) int {
    if low == high {
        return nums[low]
    }

    pos := partition(nums, low, high)
    // 满足情况，第K大
    if pos == len(nums)-k {
        return nums[pos]
    }

    if pos < len(nums)-k {
        return quickSort(nums, pos+1, high, k)
    }
    return quickSort(nums, low, pos-1, k)
}

func partition(nums []int, low, high int) int {
    // 1. 选取枢纽值（low应该替换为随机数）
    pos := nums[high]
    for low <= high {
        // 2. 低指针上移，不符合条件式替换到nums[high]
        for low < high && nums[low] <= pos {
            low++
        }
        nums[high] = nums[low]
        // 3. 高指针下移，不符合条件时替换到nums[low]
        for low < high && nums[high] >= pos {
            high--
        }
        nums[low] = nums[high]
    }
    // 归位，low最后移动，所以觉定最终位置
    nums[high] = pos
    return high
}

// 执行用时 :12 ms, 在所有 Go 提交中击败了55.08%的用户
// 内存消耗 :4 MB, 在所有 Go 提交中击败了26.32%的用户

分享：