一种思路是利用两次冒泡法,因为第一次冒泡,最大的在a[n-1],第二次冒泡后,次最大值在a[n-2]这样直接返回即可。核心代码如下:
for(int i=0; i<2; i++)
for(int j=0; j<n-i-1; j++)
{
if(a[j] >a[j+1])
swap(a[j], a[j+1]);
}
return a[n-2];
但是这样做,显然效率不够高,几乎要遍历两次,有没有遍历一次就可以找到呢?
第二种思路:
首先看源码:
int find2Max(int a[], int n)
{
int max1 = 0;
int max2 = 0;
for(int i=1; i<n; i++)
{
if(a[i] > a[max1])
{
max2 = max1;
max1 = i;
}
else if(a[i] > a[max2] && a[i] < a[max1])
max2 = i;
}
return max2;
}
首先设置两个索引max1,max2,分别用来存最大的和次最大的索引。然后遍历一次,当a[i] > a[max1]时是一种情况,要进行交换;另外当a[i] < a[max1] 同时a[i] > a[max2]时,这种情况也要进行处理。注意,max1、max2的索引初值均为0, 有的人把max2设成-1,这是不够严密的。另外,就是遍历的时候,从第二个数开始遍历即可,即i = 1开始往后遍历。
这个算法的复杂度是o(n),问题似乎很好解决了,但试问有比这更快的方法吗?而且,如果不是让找第二大的数,而是找第三大、第四大、第五大,或者第三小、第4小的数,上面这种思路显然是走不通的。肿么办? 下篇接着说。
分享到:
相关推荐
分治算法求n个数的数组中找出第二个最大元素
这个 C 语言程序包括了一个 find_second_largest 函数,该函数接受一个整数数组和数组长度作为参数,并返回数组中第二大的元素。该函数使用一个 for 循环遍历数组中的每个元素,并根据算法中的步骤来更新最大元素和...
于是,只用再针对被最大数淘汰的数构成的新数组,再次利用顺序比较找最大数,便可得到原数组的第二大的数。 3.分治策略是一种解决问题的算法设计策略,它将问题分解成更小的子问题,并通过递归地解决子问题来得到原...
本文实例讲述了Python实现找出数组中第2大数字的方法。分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城...
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...
C++语言实现查找数组中第二大和第二小的数值,并且判断数组中重复次数最高的数
剑指Offer(Python多种思路实现):...第二个指针指向数组的最后一个数字,从后向前移动,遇到奇数就停下来,交换两个指针指向的元素,直到两个指针相遇。 class Solution: def reOrderArray(self, array): # write c
本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数。这里数组可以是有重复的值! 下面是自己写的...
试设计一个O(log n)时间的算法,找出X 和Y 的2n 个数的中位数。 ★数据输入 输入数据第1 行是每个数组中元素个数n;接下来的2 行中每行有n 个整数,分别为X和Y 中元素。 ★数据输出 将计算出的X 和Y 的中位数保留一位...
西南交通大学算法分析与设计hhy实验4.2编写一个分治算法来搜索mx n矩阵matrix中的一个目标值target,该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。 4.1.1该问题的自然语言描述法 ...
该算法首先将max_sum设置为输入数组的第一个元素。 外循环访问输入数组的每个元素,作为潜在切片的起点。 内循环访问每个起点以及该起点之后的所有元素,作为潜在切片的终点。 这将创建所有可能的切片。 鉴于n...
最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...
本文实例讲述了php数组冒泡排序算法。...$j++){//需要比较$len-1次,因为循环到最后一个数时,后面没有数可以比较了,所以循环到倒数第二个数正好 $k=$j+1;//得到当前数的后一个数的下标,我们依次比较的是数组
本文实例讲述了PHP实现找出有序数组中绝对值最小的数算法。分享给大家供大家参考,具体如下: 问题: 一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值。 方法1: 遍历数组,找到绝对值...
9:数组第k大元素 p 10:原地合并有序数组 p 11:两数之和 p 12:回文串,只考虑数字字母 p 13:盛水最多的容器 14:长度最小的子数组 15:快乐数 16:字符串降序排列 17:三数之和 18:最多点共线 19:最长回文
本文实例讲述了C#求数组中元素全排列的方法。分享给大家供大家参考。具体如下: 1.算法描述 全排列的第一项是该数组的升序排列,最后一项是该数组的降序排列。本文中用到的了一个函数FindNextArray:从升序排列开始...
问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们...
40个Java算法与数组方面的源码实例集,这些代码都是比较简单,觉得很实用,有算法、数组、打印出杨辉三角形、求1 2! 3! ... 20!的和、递归方法实例、利用递归方法求阶乘之和、判断大小排序、球从100米高度自由落下,...
第2章 数学归纳法 2.1 引言 2.2 三个简单的例子 2.3 平面内区域的计数 2.4 简单的着色问题 2.5 复杂一些的加法题 2.6 一个简单的不等式 2.7 欧拉公式 2.8 图论中的一个问题 2.9 格雷码 2.10 在图上寻找无...
搜索数组中是否有“对和值”等于 x;返回下标乘积最大数;二分法搜索 low ... high 之间的最小数;计算数组的最大哈明距离;移动所有的 0 到数组末尾;Fisher-Yates洗牌算法,听起来很高大上 :P;计算第 k 个最小数...