商务网站规划建设与管理试卷,深圳龙华区住房和建设局网站,网站推广培训机构,广东软件开发公司废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【寻找第K大】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【寻找第K大】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
数组中的第K个最大元素【MID】
一道中等难度使用快排可以解决的题
题干 输入
[1,3,5,2,2],5,3返回值
2输入
[10,10,9,9,8,7,5,6,4,3,4,2],12,3返回值
9说明
去重后的第3大是8但本题要求包含重复的元素不用去重所以输出9 解题思路
使用快速排序的思路来解决快速排序Quick Sort是一种基于分治思想的排序算法它通过将数组分成较小和较大的两部分并分别对这两部分进行排序最终将整个数组排序。快速排序是一种高效的排序算法通常在平均情况下具有较快的执行速度。
下面是快速排序的基本思想和步骤 [划分]选择基准元素Pivot 从数组中选择一个元素作为基准元素。 [划分]划分Partition 将数组分成两部分使得基准元素左边的元素都小于等于基准元素右边的元素都大于基准元素。这一步骤通常称为“划分”。 [解决]递归排序 递归地对基准元素左边和右边的子数组进行排序。也就是说对小于基准元素的子数组和大于基准元素的子数组分别执行快速排序。 [合并] 合并 由于子数组都是在原数组中进行排序所以最终整个数组也就被排序了。
这些步骤使得较大问题被分解成较小的子问题这些子问题又能通过递归地应用快速排序来解决。在最好情况下每次划分都能将数组均匀分成两半这使得算法的时间复杂度为O(n log n)。
然而需要注意的是快速排序的性能高度依赖于基准元素的选择。最坏情况下如果每次划分都使数组分成极不平衡的两部分算法的时间复杂度可能会退化到O(n^2)。为了应对这种情况通常可以选择合适的基准元素如随机选择或者采用三数取中等方法。
总之快速排序是一种常用且高效的排序算法尤其适用于大规模数据的排序。
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法快速排序分治算法、二分查找 技巧双指针 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param a int整型一维数组* param n int整型* param K int整型* return int整型*/public int findKth (int[] a, int n, int K) {return quikSort(a, 0, n - 1, K);}public int quikSort(int[] a, int start, int end, int K) {// 找到基准元素的位置这个位置是第 pivot1(因为数组下标从0开始) 大的元素int pivot partion(a, start, end);if (K pivot 1 ) {// 正好命中return a[pivot] ;} else if (K pivot 1) {// K小于基准位置说明它是更大的数在基准位置左边搜索return quikSort(a, start, pivot - 1, K);} else {// K大于基准位置说明它是更小的数在基准位置右边搜索return quikSort(a, pivot 1, end, K );}}// 获取一个基准元素倒排所以大于基准元素的数在左小于基准元素的数在右private int partion(int[] a, int start, int end) {int pivotValue a[start];int i start, j end;while (i ! j) {// (a[j]只有大于基准元素才停止因为大的放基准元素左边while (a[j] pivotValue i j) {// 一定要j先走因为j先走ij就会在j的位置交汇而基准元素的左边一定要比自己大所以为了保证后续基准元素交换正确一定要保证交汇位置元素值大于等于基准元素所以要优先满足j的条件即找到大于基准元素的值并停下如果i先走在靠近交互点时i会越过大于基准元素的值与j交汇。j--;}// (a[i]只有小于基准元素才停止因为大的放基准元素左边while (a[i] pivotValue i j) {i;}if (i j) {swap(a, i, j);}}// 全部交换完后基准元素交换swap(a, start, j);return j;}// 辅助函数交换数组元素private void swap(int[] a, int i, int j) {int temp a[i];a[i] a[j];a[j] temp;}
}复杂度分析
快速排序的时间复杂度和空间复杂度如下
时间复杂度 平均情况 在平均情况下快速排序的时间复杂度为O(n log n)其中n是待排序数组的长度。这是因为每次划分都能将数组大致均匀地分成两部分导致递归的深度大约为log n而每次划分的过程需要O(n)的时间。 最坏情况 在最坏情况下如果每次划分都导致一个极不平衡的分割例如每次选取的基准元素都是当前子数组的最大或最小元素那么快速排序的时间复杂度可能退化到O(n^2)。这是因为需要执行n次划分每次划分都需要O(n)的时间。为了避免最坏情况通常采用随机选择基准元素或者三数取中法来减少极端情况的发生。 最好情况 快速排序的最好情况时间复杂度为O(n log n)与平均情况相同。这种情况发生在每次划分都能将数组准确地分成相等的两部分时。
空间复杂度
快速排序的空间复杂度主要取决于递归调用的深度和每次划分所使用的额外空间。 递归调用的深度 在递归调用中每次只需要保存一个基准元素的索引和部分数组的边界信息。因此递归调用的深度为O(log n)。 每次划分所使用的额外空间 每次划分需要O(1)的额外空间来存储基准元素和进行交换。
综合考虑快速排序的空间复杂度为O(log n)。这是因为虽然递归调用的深度为O(log n)但在每层递归中所需的额外空间是常数级别的。这使得快速排序在空间上比某些其他排序算法如归并排序更加节省。
拓展知识分治算法
分治法是一种解决问题的算法设计范式它将一个问题分解成多个相似的子问题然后解决这些子问题并将它们的解合并以得出原始问题的解。分治法的核心思想是将大问题分解成更小的、相似的子问题通过解决子问题来解决原始问题。
分治法通常包含三个步骤分解Divide、解决Conquer、合并Combine。 分解Divide 将原始问题划分为更小、相似的子问题。这一步骤通常是递归地进行的即将问题逐步分解为更小规模的子问题。 解决Conquer 递归地解决子问题。当子问题足够小可以直接求解时就停止分解转而解决这些子问题。 合并Combine 将子问题的解合并以得出原始问题的解。这是分治法的关键步骤将各个子问题的解整合起来形成更大问题的解。
分治法通常用于解决一些可以被分解成相似子问题的问题如排序、搜索、求解最短路径等。典型的分治算法包括归并排序和快速排序。以下是一个分治法的示例
归并排序 分解Divide 将数组分成两半分别对这两半进行排序。 解决Conquer 对分解得到的子数组递归地进行排序直到子数组长度足够小。 合并Combine 将排好序的子数组合并得到完整的有序数组。
分治法的优点在于它可以将问题分解成独立的子问题每个子问题的求解都相对简单。这使得算法设计和理解变得更加清晰。然而分治法有时会在子问题的合并阶段引入额外的开销因此在设计分治算法时需要权衡分解和合并的成本。
