元素选择问题
: 给定线性序集中n个元素和一个整数k(1<=k<=n),要求找出这n个元素中第k小的元素(第n-k大)。
这一问题可以演化成找最大最小值、找中位数等。
最简单思想:如果是直接找最大最小值,则可以通过N次比较来完成,其时间复杂度为O(N),空间复杂度为O(1)。除此之外,对于一般的k值,可以考虑对序列N先进行排序,然后直接定位第k个位置上的数即可。时间复杂度最好为O(N*logN)。
改进思想:
(1) 在某些特殊情况下,是很容易设计出O(N)的算法。比如最大最小值的时候。
如果k<=n/logn 找第k小的元素。我们可以通过堆排序的方法。
首先建立小顶堆,其时间复杂度为O(N)。然后每次输出堆顶元素(当前堆的最小值)后调整堆顶,其时间复杂度为O(logN)。循环k次,当第k次输出堆顶时结束。这样的时间复杂度为O(N+k*logN), 而k<=n/logn,即k接近于常数,则时间复杂度近似为O(N)。
如果k>=n-n/logn 找第k小的元素。同理可以建立一个(n-k)次输出的大顶堆即可。
当k的大小靠近n的两侧时,比如n=10,k=2或8。我们可以同归堆排序来达到近似O(N)的时间复杂度。
(2) 但一般的k值,特别是中位数的选择问题似乎就比上一种情况要难了。但事实上,我们仍然可以在O(n)的时间内解决。
可以考虑快排的分治算法,对N序列进行一次Partition。与快排不同的是,每次只对划分后的一个子数组进行处理。其算法代码如下:
//在a数组中选择第k小的数
Type select(Type a[], int low, int high, int k){
//找到的第k小的数
if(low==high) return a[low];
//一次选择划分,此时a[low..mid-1]<a[mid]<a[mid+1..high]
int mid=partition(a,low, high);
int midSize=mid-low+1;
if(k<=midSize) return select(a, low, mid, k);
else return select(a, mid+1, high, k-midSize);
}
从代码中很容易看出,在最坏情况下,这种算法和快排有着一样的蜕化现象,需要O(N^2)时间复杂度。但是在一般情况下,平均性能上可以保证近似O(N)的时间复杂度。
如果想要克服最坏情况,其基准(快排中的枢轴)的选择可以进行优化。使得基准所划分出来的两个子数组的长度至少为原数组长度的x倍(0<x<1)。具体优化策略可以参见《【JDK优化策略】java.util.Arrays的排序研究
》中的快排优化。
分享到:
相关推荐
在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...
在计算机科学领域,排列问题是一个经典且重要的主题,特别是在算法设计和分析中。当我们面对包含重复元素的排列问题时,我们需要考虑如何有效地生成所有可能的排列,并解决与这些排列相关的计算挑战。这个问题在数据...
本文将深入探讨两个经典的问题——“背包问题”和“找到数组中的第K小元素”,并结合C++代码进行解析。 首先,我们来看“背包问题”。背包问题是一个经典的优化问题,常见于组合优化和运筹学中。它的基本模型是:有...
### 算法设计与分析的经典问题解析 #### 题目1:N皇后问题(八皇后问题的扩展) **背景介绍**: N皇后问题是经典的回溯法问题之一,其核心是在N×N的棋盘上放置N个皇后,使得任意两个皇后不在同一行、同一列或同一...
这里我们关注的是一个经典的数据结构问题——背包问题。背包问题是一类优化问题,常见于运筹学、计算机科学和算法设计中。在本案例中,我们将讨论如何用C语言和栈来解决这类问题。 首先,让我们了解背包问题的基本...
《数据结构原理与经典问题求解》这本书的源代码集合为学习者提供了一个深入理解数据结构和算法的实践平台。下面将详细讨论其中可能涵盖的知识点。 1. **线性数据结构**:包括数组、链表、栈和队列。数组是最基本的...
1. **2Sum (1)**: 这是LeetCode中的经典问题,标签为 "数组" 和 "哈希表"。问题要求在给定整数数组中找出两个数,使得它们的和等于一个特定的目标值。高效的解决方案是使用哈希表,先遍历数组,对于每个元素,我们...
### 经典问题的回溯算法 #### 一、引言 在现实生活中,很多问题并不像数学问题那样可以通过公式直接解决,它们往往需要经历一系列复杂的步骤和多种可能性的探索才能找到答案。这类问题通常涉及一定的规则,而这些...
这本书“数据结构与算法经典问题解析-Java语言描述”旨在帮助读者深入理解这些概念,并通过具体的Java代码实现来提升解决实际问题的能力。 1. **数据结构**: - **数组**:是最基本的数据结构,它是一系列相同类型...
本篇文章将详细探讨减治法的概念、在C语言中的应用,以及如何利用C语言解决选择问题。 首先,减治法的核心思想是将一个大问题分解为若干个规模较小的子问题,然后分别解决这些子问题,最后将子问题的解组合起来得到...
在算法的学习过程中,理解和掌握经典问题的解决方案是至关重要的一步。这些经典问题往往源于实际应用,经过抽象和简化,成为了检验和提升算法设计能力的理想工具。例如,书中的题目可能涵盖排序、搜索、图论、动态...
穷举搜索法的一个经典例子是排列问题,比如如何将一组变量排成特定的几何图形,使得图形的特定属性达到预期值。在这个过程中,每一个可能的排列都需要被考虑。程序通过嵌套循环来逐一生成这些排列,并检查每个排列...
根据给定文件的信息“Java经典问题算法大全”,我们可以推断出这份资料主要涵盖了Java编程语言中的经典算法问题及其解决方案。接下来,我们将详细探讨这一主题下的关键知识点。 ### 一、基础知识回顾 在深入讨论...
通过以上各种方法,我们可以根据项目需求和浏览器兼容性选择合适的方案解决元素容器内的垂直居中问题。在实际工作中,了解并熟练掌握这些技巧,将有助于提高开发效率和代码质量。 压缩包内的 "img_vertical" 文件...
【旅行商问题】旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题,它描述了一个旅行商如何规划行程,以便访问每个城市一次并返回起点,同时使总路程最短。在这个问题中,旅行商需要找到一个...
经典问题如二分搜索,通过不断将数组或集合划分为两半,快速定位目标元素;大整数乘法利用分治策略降低计算复杂度;Strassen矩阵乘法优化了传统矩阵乘法;棋盘覆盖问题和合并排序则展示了分治如何在解决组合问题和...
《C++数据结构原理与经典问题求解》一书配套的源代码涵盖了数据结构和算法在C++语言中的实现,是深入理解数据结构并解决实际编程问题的重要资源。本资料库包含了各种数据结构如数组、链表、栈、队列、树、图以及常用...
在“经典问题求解”部分,可能涵盖了诸如排序(冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等)、搜索(线性搜索、二分搜索、深度优先搜索、广度优先搜索等)、图算法(最短路径、最小生成树、拓扑...