欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数字之魅:寻找数组中的最大值和最小值

程序员文章站 2022-07-27 17:04:06
数组是最简单的一种数据结构。我们经常碰到的一个基本问题,就是寻找整个数组中最大的数,或者最小的数。这时,我们都会扫描一遍数组,把最大(最小)的数找出来。如果我们需要同时找出最大和最...

数组是最简单的一种数据结构。我们经常碰到的一个基本问题,就是寻找整个数组中最大的数,或者最小的数。这时,我们都会扫描一遍数组,把最大(最小)的数找出来。如果我们需要同时找出最大和最小的数呢?

对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来呢?

这个题目比价简单,主要方案如下:

方案一:分别求最大和最小值。这是一种比较常规的解法。可以分别求出数组的最大值和最小值,这样,我们可以采用最基本的冒泡思想遍历两次(2N)就能求解。

方案二:分组求解。由于前面的需要遍历2N次。这里为了使其遍历的次数减少,我们可以采用分组。

(1) 按顺序将数组中相邻的两个数分在同一组,逻辑上分组,实际什么都不用做;

(2) 比较同一组的两个数,将大的数放在偶数位上,小的放在奇数位上;

(3) 最后,从偶数位上求最大值,奇数位上求最小值即可。

这样一共需要比较1.5N次。这种办法虽然比较次数变少了,但却破坏了原数组,因为我们交换了数组数据的位置。

方案三:改进的分组。此种方法可以避免破坏原数据的顺序。

(1) 用两个变量max和min分别存储当前的最大值和最小值。

(2) 同一组的两个数比较完之后,不再调整顺序,将其中较大的与当前max比较,较小的与min比较;

(3) 如此反复,直到遍历完整个数组。

整个过程比较次数也为1.5N次,但是没有对原数据进行更改,如果数据是在只读存储区,那么该方法就能派上用场了。

方案四:分治策略。该方法用到归并排序中的merge()函数,虽然方法不一样,但是可惜的比较的次数还是没有减少,仍然为1.5N次。在求解的过程中分别求出前后N/2个数的min和max,然后,取较小的min,较大的max即可。

这里主要是提醒一下经常用的两种思路:快排你的partion()和归并里的merge(),这两个函数的解决问题的思路十分常用。通常在解决问题的时候,要想到他们,是一种解决的思路。

扩展问题

如果需要找出N个数中的第二大数,需要比较多少次呢?是否可以使用类似的分治思想来降低比较的次数呢?

思路一:

用两个变量分别存最大值max1和次大值max2,遍历数组:

初始化:max1=arr[0],max2=0;

先与max2比较,如果比max2大再和max1比较;

如果arr[i] >max1,则更新max=arr[i],max2=max1;

否则如果arr[i] > max2 && arr[i]< max1,则更新max2=arr[i];

否则,不进行更新操作。

这个方法最多的比较次数为2*N次,最大的值在最后面;最小N次第一个和第二个恰好就是最大和第二大的数。

思路二:快速选择算法的思想。

先寻找出第k大的整数,然后再通过两次遍历前k大的数字找出第二大的数字,因为找出的前k个元素是不保证排序的。比较的次数为:找出前K个元素次时:最好k次,最坏N次。然后在前k个元素中找出第K个元素:比较的次数:k+k-1次。所以比较的次数为:最好3k-1次,最坏:N+2k-1次。