【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)

2024-04-15 22:44
文章标签 java leetcode 算法 实现 数组 元素 说明 经典 最大 python3 注释 medium 215

本文主要是介绍【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页： 进朱者赤

阿里非典型程序员一枚 ，记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

目录

  • 题目描述
  • 思路及实现
    • 方式一：快速选择排序
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
    • 方式二：最小堆（最小优先队列）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
  • 总结
  • 相似题目

  • 标签(题目类型)：数组

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

原题：LeetCode 215

思路及实现

方式一：快速选择排序

思路

快速选择算法是快速排序的一个变种，用于在未排序的列表中找到第 k 小（或第 k 大）的元素。该算法的核心思想是利用快速排序的分区过程来定位目标元素。在分区过程中，我们选择一个枢轴（pivot）元素，并将数组划分为两部分：一部分包含比枢轴小的元素，另一部分包含比枢轴大的元素。如果枢轴的位置正好是我们想要找的 k 的位置，那么算法结束；如果枢轴的位置在 k 的左侧，那么目标元素必定在枢轴的右侧；反之亦然。

代码实现

Java版本
public class Solution {  /**  * 找到数组中第k大的元素  *  * @param nums   待搜索的数组  * @param k      要查找的是第k大的元素  * @return       返回第k大的元素  */  public int findKthLargest(int[] nums, int k) {  int n = nums.length; // 数组长度  int targetIndex = n - k; // 要找的是第k大的元素，在排序后的数组中对应的索引位置  return quickSelect(nums, 0, n - 1, targetIndex); // 调用快速选择算法查找目标元素  }  /**  * 快速选择算法的核心实现  *  * @param nums         待搜索的数组  * @param left         搜索区间的左边界  * @param right        搜索区间的右边界  * @param targetIndex  目标元素在排序后数组中的索引位置  * @return             返回目标元素的值  */  private int quickSelect(int[] nums, int left, int right, int targetIndex) {  if (left == right) {  // 如果左右指针相等，说明区间内只有一个元素，直接返回该元素  return nums[left];  }  // 调用分区操作，返回枢轴元素的索引位置  int pivotIndex = partition(nums, left, right);  if (pivotIndex == targetIndex) {  // 如果枢轴位置恰好等于目标位置，直接返回枢轴元素  return nums[pivotIndex];  } else if (pivotIndex < targetIndex) {  // 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间  return quickSelect(nums, pivotIndex + 1, right, targetIndex);  } else {  // 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间  return quickSelect(nums, left, pivotIndex - 1, targetIndex);  }  }  /**  * 数组分区操作，选取枢轴元素，将小于枢轴的元素移动到左侧，大于枢轴的元素移动到右侧  *  * @param nums    待分区的数组  * @param left    分区的左边界  * @param right   分区的右边界  * @return        返回枢轴元素的索引位置  */  private int partition(int[] nums, int left, int right) {  int pivot = nums[right]; // 选取最右边的元素作为枢轴  int i = left; // 初始化左侧指针  for (int j = left; j < right; j++) {  // 将小于枢轴的元素移动到左侧  if (nums[j] <= pivot) {  swap(nums, i, j); // 交换元素  i++; // 左指针右移  }  }  swap(nums, i, right); // 将枢轴移动到正确的位置  return i; // 返回枢轴元素的索引位置  }  /**  * 交换数组中两个元素的位置  *  * @param nums 数组  * @param i    第一个元素的索引  * @param j    第二个元素的索引  */  private void swap(int[] nums, int i, int j) {  int temp = nums[i];  nums[i] = nums[j];  nums[j] = temp;  }  
}

说明：
该代码首先定义了一个 findKthLargest 方法，它接受一个整数数组 nums 和一个整数 k 作为输入，返回第 k 大的元素。该方法使用快速选择算法来定位目标元素。在 partition 方法中，我们随机选择一个枢轴元素，并对数组进行分区。swap 方法用于交换数组中两个元素的位置。

C语言版本
#include <stdio.h>  /**  * @brief 数组分区操作  *  * 将数组 nums 中小于等于枢轴的元素移动到左侧，大于枢轴的元素移动到右侧。  *  * @param nums    待分区的数组  * @param left    分区的左边界  * @param right   分区的右边界  * @return        返回枢轴元素的索引位置  */  
int partition(int* nums, int left, int right) {  int pivot = nums[right]; // 选取最右边的元素作为枢轴  int i = left; // 初始化左侧指针  for (int j = left; j < right; j++) {  // 将小于等于枢轴的元素移动到左侧  if (nums[j] <= pivot) {  int temp = nums[i];  nums[i] = nums[j];  nums[j] = temp;  i++; // 左指针右移  }  }  int temp = nums[i];  nums[i] = nums[right];  nums[right] = temp; // 将枢轴移动到正确的位置  return i; // 返回枢轴元素的索引位置  
}  /**  * @brief 快速选择算法的核心实现  *  * 查找数组中第 targetIndex 大的元素。  *  * @param nums         待搜索的数组  * @param left         搜索区间的左边界  * @param right        搜索区间的右边界  * @param targetIndex  目标元素在排序后数组中的索引位置  * @return             返回目标元素的值  */  
int quickSelect(int* nums, int left, int right, int targetIndex) {  if (left == right) {  // 如果左右指针相等，说明区间内只有一个元素，直接返回该元素  return nums[left];  }  // 调用分区操作，返回枢轴元素的索引位置  int pivotIndex = partition(nums, left, right);  if (pivotIndex == targetIndex) {  // 如果枢轴位置恰好等于目标位置，直接返回枢轴元素  return nums[pivotIndex];  } else if (pivotIndex < targetIndex) {  // 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间  return quickSelect(nums, pivotIndex + 1, right, targetIndex);  } else {  // 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间  return quickSelect(nums, left, pivotIndex - 1, targetIndex);  }  
}  /**  * @brief 查找数组中第k大的元素  *  * @param nums   待搜索的数组  * @param numsSize 数组的长度  * @param k      要查找的是第k大的元素  * @return       返回第k大的元素  */  
int findKthLargest(int* nums, int numsSize, int k) {  int targetIndex = numsSize - k; // 要找的是第k大的元素，在排序后的数组中对应的索引位置  return quickSelect(nums, 0, numsSize - 1, targetIndex); // 调用快速选择算法查找目标元素  
}  /**  * @brief 主函数  *  * 执行查找数组中第k大的元素的操作，并输出结果。  *  * @return 0 表示程序正常退出  */  
int main() {  int nums[] = {3, 2, 1, 5, 6, 4}; // 待搜索的数组  int k = 2; // 要查找的是第2大的元素  int n = sizeof(nums) / sizeof(nums[0]); // 数组的长度  int result = findKthLargest(nums, n, k); // 调用函数查找第k大的元素  printf("The %dth largest element is: %d\n", k, result); // 输出结果  return 0; // 程序正常退出  
}

说明：
main函数作为程序的入口点，包含了测试代码，用于验证快速选择算法的正确性。

Python3版本
def findKthLargest(nums, k):  # 要找的是第k大的元素，相当于在排序后的数组中找倒数第k个元素  target_index = len(nums) - k  # 使用快速选择算法查找目标元素  return quick_select(nums, 0, len(nums) - 1, target_index)  # 快速选择算法实现  
def quick_select(nums, left, right, target_index):  if left == right:  # 如果左右指针相等，则直接返回该位置的元素  return nums[left]  # 选取枢轴  pivot_index = partition(nums, left, right)  if pivot_index == target_index:  # 如果枢轴位置恰好等于目标位置，直接返回枢轴元素  return nums[pivot_index]  elif pivot_index < target_index:  # 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间  return quick_select(nums, pivot_index + 1, right, target_index)  else:  # 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间  return quick_select(nums, left, pivot_index - 1, target_index)  # 数组分区操作  
def partition(nums, left, right):  # 选取最右边的元素作为枢轴  pivot = nums[right]  pivot_index = left  for i in range(left, right):  # 将小于枢轴的元素移动到左侧
if nums[i] <= pivot:
nums[pivot_index], nums[i] = nums[i], nums[pivot_index]
pivot_index += 1
# 将枢轴移动到正确位置
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
return pivot_index

说明：
快速选择（QuickSelect）算法，用于在未排序的数组中找到第target_index小的元素。快速选择算法是快速排序算法的一个变种，用于解决未排序数组中的第k小（或大）元素问题。
通过递归地分区数组，并在每个分区中查找目标元素，从而高效地找到第target_index小的元素。由于快速选择算法的平均时间复杂度为O(n)，其中n是数组的长度，因此它在处理大型数据集时非常有效

复杂度分析

  • 时间复杂度：在平均情况下，快速选择算法的时间复杂度为O(n)，其中n为数组的元素个数。最坏情况下的时间复杂度为O(n^2)，但平均情况下仍然是O(n)。

  • 空间复杂度：快速选择算法的空间复杂度主要取决于递归调用的栈空间。最坏情况下的空间复杂度为O(n)，但平均情况下为O(logn)。

快速选择算法是一种高效的解决方案，能够在无序数组中快速地找到第k个最大或最小元素。它具有较低的平均时间复杂度和较小的平均空间复杂度。

方式二：最小堆（最小优先队列）

思路

使用一个最小堆（最小优先队列）来维护当前最大的 k 个元素。遍历数组，对于每个元素，如果堆的大小小于 k，则直接将其加入堆中；如果堆的大小等于 k，则比较当前元素与堆顶元素的大小，如果当前元素更大，则弹出堆顶元素，将当前元素加入堆中。最后堆顶元素即为第 k 个最大的元素。

代码实现

Java版本
import java.util.PriorityQueue;class Solution {public int findKthLargest(int[] nums, int k) {// 创建最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 初始化堆for (int i = 0; i < k; i++) {minHeap.offer(nums[i]);}// 维持堆的大小为kfor (int i = k; i < nums.length; i++) {if (nums[i] > minHeap.peek()) {minHeap.poll();minHeap.offer(nums[i]);}}// 返回第k大的元素return minHeap.peek();}
}

说明：
虽然代码使用最小堆来解决问题，但返回的是第k大的元素，因为堆中始终保存着最大的k个元素，且堆顶是最小的那个。如果需要找第k小的元素，则无需任何修改；但如果要找第k大的元素，并希望代码更加直观，可以考虑使用最大堆或者对数组进行降序排序后再使用最小堆。

C语言版本
#include<stdlib.h>int findKthLargest(int* nums, int numsSize, int k) {// 创建最小堆int* minHeap = (int*)malloc(sizeof(int) * k);int i;// 初始化堆for (i = 0; i < k; i++) {minHeap[i] = nums[i];}buildMinHeap(minHeap, k);// 维持堆的大小为kfor (i = k; i < numsSize; i++) {if (nums[i] > minHeap[0]) {minHeap[0] = nums[i];heapify(minHeap, k, 0);}}// 返回第k大的元素int result = minHeap[0];free(minHeap);return result;
}void buildMinHeap(int* array, int size) {int i;for (i = (size - 2) / 2; i >= 0; i--) {heapify(array, size, i);}
}void heapify(int* array, int size, int index) {int left = 2 * index + 1;int right = 2 * index + 2;int smallest = index;if (left < size && array[left] < array[smallest]) {smallest = left;}if (right < size && array[right] < array[smallest]) {smallest = right;}if (smallest != index) {swap(&array[index], &array[smallest]);heapify(array, size, smallest);}
}void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}

说明
代码首先创建一个大小为k的最小堆，并使用数组的前k个元素初始化它。然后，它遍历数组的剩余部分，每次遇到比堆顶元素大的元素时，就替换堆顶元素并重新调整堆。最后，返回堆顶元素，即第k大的元素。这种方法的时间复杂度是O(n log k)，其中n是数组的大小。

Python3版本
import heapq  # 导入heapq模块，用于操作堆  class Solution:  def findKthLargest(self, nums: List[int], k: int) -> int:  # 创建一个空的最小堆  minHeap = []  # 初始化堆  # 将数组的前k个元素添加到最小堆中  for i in range(k):  heapq.heappush(minHeap, nums[i])  # 遍历数组的剩余部分  # 维持堆的大小为k，确保堆顶元素始终是堆中最小的元素  for i in range(k, len(nums)):  # 如果当前元素大于堆顶元素，那么弹出堆顶元素，并将当前元素压入堆中  # 这样，堆顶元素始终是遍历过的元素中第k大的元素  if nums[i] > minHeap[0]:  heapq.heappop(minHeap)  heapq.heappush(minHeap, nums[i])  # 最后，堆顶元素就是第k大的元素  # 因为堆的大小始终为k，所以堆顶元素就是遍历过的k个最大元素中最小的那个，即第k大的元素  return minHeap[0]

说明：
导入heapq模块，这是Python标准库中的一个模块，用于实现堆队列算法。
虽然这段代码使用了一个最小堆来解决问题，但返回的实际上是第k大的元素，因为堆中始终保存着最大的k个元素，而堆顶是最小的那个。这意味着，如果我们需要找到第k小的元素，则这段代码可以直接使用。如果要找第k大的元素，则需要将数组逆序或者调整k的值（即使用len(nums) - k + 1作为目标位置）

复杂度分析

  • 时间复杂度： 建立初始堆的时间复杂度为O(k * logk)，维护堆的大小为k的时间复杂度为O((n - k) * logk)，总时间复杂度为O(n * logk)。
  • 空间复杂度： 最小堆所使用的空间为O(k)。

总结

最小堆快速选择算法
优点- 简单易实现- 高效，能找到第k个最大或最小元素
- 适用于动态数据流- 原地操作，不需要额外空间
缺点- 空间复杂度较高- 平均情况下较高时间复杂度
时间复杂度- 平均：O(nlogk)- 平均：O(n)
- 最差：O(nlogk)- 最差：O(n^2)
空间复杂度- O(k)- 平均：O(logn)
- 最差：O(n)
其他- 用于处理动态数据流- 快速选择是快速排序的关键步骤

最小堆的优点在于实现简单，适用于动态数据流，但其空间复杂度较高，需要额外的空间来存储堆。
快速选择算法的优点在于高效，能够快速找到第k个最大或最小元素，并且是原地操作，不需要额外空间。快速选择是快速排序算法的关键步骤之一，利用分治思想进行划分并维护子区间的方式进行快速查找。
最小堆的时间复杂度是平均和最差情况下都是O(nlogk)，空间复杂度为O(k)。
快速选择算法的时间复杂度是平均情况下为O(n)，最差情况下为O(n^2)（当数组完全有序时），空间复杂度为平均情况下O(logn)，最差情况下为O(n)。
综上所述，最小堆适用于处理动态数据流，实现简单但空间复杂度较高；而快速选择算法在平均情况下具有较低的时间复杂度和较小的空间复杂度，但最差情况下时间复杂度较高。因此，根据情况选择合适的算法来解决特定的问题。

相似题目

题目名题目链接难度
leetcode 703. 数据流中的第K大元素链接简单
leetcode 973. 最接近原点的K个点链接中等
leetcode 215. 数组中的第K个最大元素链接中等
leetcode 347. 前K个高频元素链接中等
leetcode 378. 有序矩阵中第K小的元素链接中等

以上是一些与LeetCode 215题相似的题目，它们都涉及到在数组、数据流或矩阵中查找第K个最大或最小元素的问题。它们的难度不同，有简单和中等难度的题目

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

  • 关于我：阿里非典型程序员一枚 ，记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️

这篇关于【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/907134。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Zookeeper安装和配置说明

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种，单机模式和集群模式以及伪集群模式。 ■ 单机模式：Zookeeper只运行在一台服务器上，适合测试环境； ■ 伪集群模式：就是在一台物理机上运行多个Zookeeper 实例； ■ 集群模式：Zookeeper运行于一个集群上，适合生产环境，这个计算机集群被称为一个“集合体”（ensemble） Zookeeper通过复制来实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2