LeetCode算法题(Go语言实现)_49

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

一、代码实现（快速选择算法）

import (
	"math/rand"
	"time"
)

func findKthLargest(nums []int, k int) int {
	rand.Seed(time.Now().UnixNano())
	return quickSelect(nums, 0, len(nums)-1, k)
}

func quickSelect(nums []int, left, right, k int) int {
	if left == right {
		return nums[left]
	}

	pivotIndex := rand.Intn(right-left+1) + left
	pivotVal := nums[pivotIndex]

	// 三路分区
	low, mid, high := left, left, right
	for mid <= high {
		if nums[mid] > pivotVal {
			nums[low], nums[mid] = nums[mid], nums[low]
			low++
			mid++
		} else if nums[mid] == pivotVal {
			mid++
		} else {
			nums[mid], nums[high] = nums[high], nums[mid]
			high--
		}
	}

	leftLength := low - left
	if k <= leftLength {
		return quickSelect(nums, left, low-1, k)
	}

	midLength := high - low + 1
	if k <= leftLength+midLength {
		return pivotVal
	}

	return quickSelect(nums, high+1, right, k-(leftLength+midLength))
}

二、算法分析

1. 核心思路

• 快速选择算法：基于快速排序的分治思想，但每次仅递归处理包含目标的子数组。
• 三路分区：将数组划分为大于、等于、小于基准值的三部分，减少不必要的递归。
• 随机基准：随机选择基准值避免最坏情况，确保平均时间复杂度为O(n)。

2. 关键步骤

1. 随机基准选择：随机选取一个元素作为基准值pivotVal。
2. 三路分区操作：
   • low指针左侧元素均大于pivotVal。
   • mid遍历数组，将元素分类到对应区域。
   • high指针右侧元素均小于pivotVal。
3. 递归决策：
   • 若左区长度≥k，递归处理左区。
   • 若k在左区和中区总长内，直接返回pivotVal。
   • 否则递归处理右区，调整k值。

3. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 全相同元素：如[3,3,3], k=2，直接返回3。
• k=1或k=n：处理最大或最小元素。
• 逆序/顺序数组：随机基准确保效率。

2. 扩展应用

• 前k大元素：修改返回逻辑收集元素。
• 流式数据：结合堆结构处理动态数据。
• 多维数据：定义合适比较规则处理复杂结构。

3. 多语言实现

import random

def findKthLargest(nums, k):
    def quick_select(left, right, k):
        if left == right:
            return nums[left]
        pivot_index = random.randint(left, right)
        pivot_val = nums[pivot_index]
        low, mid, high = left, left, right
        while mid <= high:
            if nums[mid] > pivot_val:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == pivot_val:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
        if k <= low - left:
            return quick_select(left, low-1, k)
        elif k <= (low - left) + (high - low +1):
            return pivot_val
        else:
            return quick_select(high+1, right, k - (low - left + high - low +1))
    return quick_select(0, len(nums)-1, k)

import java.util.Random;

public class Solution {
    private static final Random rand = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int pivotIndex = rand.nextInt(right - left + 1) + left;
        int pivotVal = nums[pivotIndex];
        int low = left, mid = left, high = right;
        while (mid <= high) {
            if (nums[mid] > pivotVal) {
                swap(nums, low++, mid++);
            } else if (nums[mid] == pivotVal) {
                mid++;
            } else {
                swap(nums, mid, high--);
            }
        }
        int leftLen = low - left;
        if (k <= leftLen) return quickSelect(nums, left, low - 1, k);
        int midLen = high - low + 1;
        if (k <= leftLen + midLen) return pivotVal;
        return quickSelect(nums, high + 1, right, k - (leftLen + midLen));
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

五、总结与优化

1. 算法对比

2. 工程优化

• 尾递归优化：减少递归栈深度。
• 迭代实现：改用循环结构避免栈溢出。
• 内存优化：处理原数组避免额外空间。

3. 扩展方向

• 并行处理：多线程加速分区过程。
• 适应性优化：根据数据分布自动选择策略。
• 稳定性增强：处理元素相等时的稳定性需求。