`

寻找第2小元素

阅读更多

分析: 看见题目中有lg(n) 项,首先应该想到的是分治法,算法的思路如下:(为简单起见,不考虑取整的问题)

将 n 个元素分成 n/2 对.每一对之间互相比较.这样一共比较了 n/2 次.然后将每一对的较小元素放在 S[1...n/2] 数组中,较大的元素对应的放在 B[1...n/2]中.显然最小的元素肯定在数组S中,那么第2小的元素(设代号为X)  是否也在 S 中呢?

首先,假设第2小元素X在数组S 中,因为最小的元素也在数组S中,所以X在S中同样也肯定是第2小元素.这样我们可以递归的在S中继续寻找第2小元素,并将搜索的范围缩小了一半.

如果第2小元素X不在数组S中,(即在数组B中),由上面的分区算法知,在B中的元素必然大于相应位置上S中的元素.在这里X是第2小元素,它仅大于最小元素.所以它在B中的位置与最小元素在S中的位置相同.

综上可知:第2小元素X要么是S中的第2小元素,要么是B中位置与最小元素在S中的位置相同的元素.

这样算法就很明了了: 将 n 个元素分成 n/2 对比较,较大者放入B,较小者放入S,若B和S的大小为1,则B[1]作为第2小元素返回,S[1]作为最小元素返回(主要是想得到最小元素在S中的位置),若B和S的大小大于1,则递归的在S中寻找最小元素和第2小元素,并将S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较(有点拗口),其中较小者便是真正的第2小元素.

举个例子吧,如:   在序列 3,2,5,8,6,4,9,7 中寻找第2小元素.

过程:首先分在[3,2] [5,8] [6,4] [9,7] 四组,经比较后得到 S1=2,5,4,7    B1=3,8,9,7.

        再将 S1分区,得到  S2=2,4   B2=5,7 .

        S2中最小值是2,第2小元素是4. B2中与S2中最小值对应的是5,因4小于5.所以得到S1的最小值是2,第2小元素是4, 在B1中与S1中最小值2对应的是3,因4>3,所以得到 整个序列的第2小元素为 3.完成.

算法分析: T(n)=n/2+T(n/2)+1   //其中的n/2是分区时比较的次数,1 是递归时S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较的消耗.

                  T(2)=1.

解递归式即可:T(n)=n+lg(n)-2 .

 

 

另解:

 

 

step1:对所有元素,两个一组比较大小,小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。

step2:沿着树从树根向下到叶子,找出第二小的元素,比较次数是ceil[lgn]-1。令m2[p]表示以p为根的树中的第二小元素。对于当前处理结点为p,key[p] = min{key[left[p]], key[right[p]]}。假设key[p] =  key[left[p]],则m2[p] = min{m2[left[p]], key[right[p]]}

 

分享到:
评论

相关推荐

    寻找第k小元素 基本算法复习

    在计算机科学和编程领域,寻找第k小元素是一项常见的任务,它涉及到排序和搜索算法的知识。这个主题是对基本算法的复习,旨在强化我们对高效解决问题的理解。在此,我们将深入探讨几种寻找第k小元素的算法,并分析...

    寻找第k小元素(vc)

    在编程领域,寻找第k小元素(或第k大元素)是常见的算法问题,它涉及到对数据集合的排序和查找。在这个问题中,我们要在数组中找到第k个最小的元素,同时考虑到数组中可能存在重复的元素。这个问题在实际应用中广泛...

    python线性时间内寻找元素(递归与分治)

    【问题描述】每次都是优化选出一个元素(分组后的中位数)为划分基准,在线性时间内寻找第i小元素。提示:分组时的组的个数为n/5的向下取整;分组后的中位数取第(num_group/2向上取整)小的元素。 【输入形式】在...

    算法:求第k小元素

    它的基本思想是利用分治法来寻找第k小的元素。首先,选取一个枢轴元素,将数组分为小于枢轴和大于枢轴的两部分。如果k位于枢轴的左边,则在左边的部分继续找;如果k位于枢轴的右边,则在右边的部分找。通过递归,...

    背包问题,第K小元素等算法代码及描述

    在解决背包问题时,可能会用到一维或二维数组来表示状态,而在寻找第K小元素时,可能会用到堆(优先队列)或者快速选择中的分区结构。理解这些数据结构的原理和操作,能帮助我们更好地设计和分析算法。 总的来说,...

    查找第i小的元素

    压缩包中的"ran_select.c"文件很可能是一个C语言实现的随机化选择算法,用于解决寻找第i小元素的问题。C语言是一种强大的系统级编程语言,它的效率高且可以直接操作内存,因此常用于编写底层算法。 现在,让我们...

    求解第K小元素,找中位数

    找中值和第k小元素,找出A[1...N]中第k小元素.找第K小元素 需要找中位数: 如果有偶数个,则找第n/2或n/2+1个小元素则可找到中位数; 如果有奇数个,则找第n/2+1个小元素则可找到中位数。

    第k小元素查找C++程序实现

    中位选择法是一种高效寻找数组中第k小(大)元素的方法。它的核心思想是快速找到数组的中位数,然后根据中位数将数组分为两部分,如果k小于中位数的位置,则在左半部分继续寻找;反之,在右半部分寻找。这个过程...

    合并排序算法,快速排序算法,递归,分治

    **寻找第k小元素** 寻找一个数组中的第k小元素可以使用分治策略。一种常见的方法是“快速选择算法”,它类似于快速排序,但只对找到第k小元素所需的部分进行排序。通过每次选择一个元素与第k小元素的候选值进行比较...

    第k小元素 算法分析与设计 四种算法实现

    - **缺点**:最坏情况下时间复杂度为O(n^2),但这种情况在寻找第k小元素时不太可能出现。 3. **中位数法**: - **概念**:中位数法是通过寻找数组的中位数来划分数据,使得划分后的两部分大小大致相等,进一步...

    算法实习:分治算法求n个数的数组中找出第二个最大元素

    通过对上述代码的分析,我们可以清晰地看到如何利用分治策略有效地解决寻找数组中第二大元素的问题。这种方法不仅提高了算法的执行效率,还使得代码更加简洁和易于理解。此外,分治法还可以应用于许多其他问题,如...

    算法题示例-寻找数组中的第二大元素.rar

    算法题目:寻找数组中的第二大元素 题目描述: 给定一个非空整数数组,找出并返回其中第二大的元素。如果没有第二大的元素,则返回 -1。 输入示例: [1, 2, 3, 4] 输出示例: 3 解题思路: 初始化两个变量,first...

    算法中最小K元素的选择问题

    例如,堆排序算法可以在O(n log k)的时间内找到前K小的元素,通过构建一个大小为K的小顶堆,然后依次处理剩余的元素,如果遇到的元素比堆顶元素小,则替换堆顶元素并调整堆。这种方法适用于需要频繁查询不同K值的...

    分治算法求最大值与最小值,找最小元素

    4. 递归地在相应子数组中继续寻找第k个最小元素,直到找到为止。 压缩包中的`main.c`可能是实现这些算法的C语言源代码,`0225.doc`可能包含算法的详细解释或解题步骤,而`main.exe`和`工程1.exe`则是编译后的可执行...

    求数列中的第1~k小元素

    - 如果基准位置大于k,则在基准左侧的子数组中继续寻找第k小的元素; - 如果基准位置小于k,则在基准右侧的子数组中继续寻找第(k-pivot位置)小的元素。 4. **终止条件**:当处理的数组长度小于某个阈值(如44)时...

    取数组中的第2大值

    "取数组中的第2大值"是一个非常明确的标题,它告诉我们需要从给定的数组中找出第二大的元素的下标和值。这个问题非常常见,在实际编程中经常会遇到这种情况。 描述解释 "c语言实现取数组中的第2大值"是标题的详细...

    algo_third_第k小元素c++_

    在编程领域,寻找一个数组中的第k小元素是一项常见的任务,尤其在算法设计和数据结构的学习中占有重要地位。这个任务通常涉及到排序和查找技术,而在这个特定的案例中,我们使用C++语言来实现,并且采取了一种将元素...

    用分治法实现元素选择

    在计算机科学中,分治...在实际编程中,这种算法不仅适用于寻找第k小元素,还广泛应用于排序(如快速排序)、查找(如二分查找)等多种场景。熟练掌握分治法及其应用,对于提升编程技能和解决复杂问题的能力至关重要。

    Java寻找第k小

    首先,让我们深入了解一下寻找第k小元素的基本算法。在没有排序的情况下,找到第k小的元素有多种方法: 1. **快速选择算法**:基于快速排序的思想,每次选取一个枢轴元素,将数组分为两部分,如果枢轴位置比k大,则...

    最小元素法

    最小元素法是解决运输问题的一种直观且有效的策略,尤其适用于寻找初始基本可行解。通过理解其原理和步骤,考生不仅能够更好地准备软考,还能在实际工作中有效地应用这一方法,解决复杂的物流和资源分配问题。

Global site tag (gtag.js) - Google Analytics