从一个数组中找最大元素和最小元素

作者：独行小刀 | 来源：互联网 | 2023-05-18 15:20

从一个数组中找最大元素和最小元素，要求总比较次数小于2n-2，（注：n为数组长度）

19 个解决方案

#1

int min,max;
min=s[0];
max=s[0];
for(i=1;i      {
  if(min   if(max>s[i])max=s[i];
  }

#2

int MaxKey(int a[] ,int n)
{
  int temp;
  if ( n == 1)
        return a[0];
  temp = MaxKey(a,n-1);
  if (temp > a[n-1])
        return temp;
  else
        return a[n-1];
}

#3

求最小数
int MinKey(int a[] ,int n)
{
  int temp;
  if ( n == 1)
        return a[0];
  temp = MinKey(a,n-1);
  if (temp < a[n-1])
        return temp;
  else
        return a[n-1];
}

#4

int min,max;
min=s[0];
max=s[0];
for(i=1;i   {
   if(s[i]      min=s[i];
   else if(s[i]>max)
        max=s[i];
  }

#5

int min1,min2,max1,max2;
min1 = s[0];
max1 = s[0];
min2 = s[n-1];
max2 = s[n-1];
int maxcount;
int min,max;
maxcount = (n%2==0?n/2:n/2+1);
for(i=1;i {
   if(min1>s[i])
   {
      min1=s[i];max1=min1;
   }
   if(min2>s[n-1-i])
   {
      min2=s[n-1-i];
      max2=min2;
   }
}
min = (min1>=min2?min2:min1);
max = (max1<=max2?max2:max1);

#6

所有楼上的都是大于等于2n-2次的！！
#include
using namespace std;

bool MinMax(int w[], int n, int& Min, int& Max)
{
if (n < 1) return false;
if (n == 1)
{
Min = Max = 0;
return true;
}
int s;
if (n % 2) {
Min = Max = 0;
s = 1;
}
else
{
if (w[0] > w[1])
{
Min = 1;
Max = 0;
}
else
{
Min = 0;
Max = 1;
}
s = 2;
}
for (int i = s; i < n; i += 2)
{
if (w[i] > w[i+1])
{
if (w[i] > w[Max]) Max = i;
if (w[i+1] < w[Min]) Min = i + 1;
}
else
{
if (w[i+1] > w[Max]) Max = i + 1;
if (w[i] < w[Min]) Min = i;
}
}
return true;
}
int main()
{
int w[10] = {414,24331,12334,54,532,5432,542352,4523452,234,245};
int max,min;
MinMax(w,10,min,max);
cout< return 0;
}

#7

int min,max;
min=s[0];
max=s[0];
for(i=1;i      {
  if(min   else if(max>s[i])max=s[i];
  }

#8

UPCC(杂食动物) 牛！

#9

设两个单元分别保存当前最大，最小值，然后依次和数组中各元素比较，如果比当前最大还要大，那自然不用再跟当前最小的那各比较，对求最小值也同理，介于当前最大，最小值之间则要比较两次，不过总共比较次数肯定小于2(n-1)=2n-2次

#10

UPCC(杂食动物):

如果是10个数,你的比较次数可能会达20次
if (n < 1) return false; 1次
if (n == 1)         1次
for (int i = s; i < n; i += 2)   5次
if (w[i] > w[i+1])               5次
if (w[i] > w[Max]) Max = i;      5次
if (w[i+1] < w[Min]) Min = i + 1;  5次
这样的话你就有22次比较了

#11

#include "stdio.h"
int main()
{
int s[15]= {123,324,235,3124,345,2134,43,123,512,12,12,34,12,445,14325};
int n=sizeof(s)/4;
printf("%d\n",n);
int min1,min2,max1,max2;
min1 = s[0];
max1 = s[0];
min2 = s[n-1];
max2 = s[n-1];
int maxcount;
int min,max;
maxcount = (n%2==0?n/2:n/2+1);
int i,j=0;
for(i=1;i {
   if(min1>s[i])
   {
      min1=s[i];
  j++;
   }
   else if(max1    {
   max1=s[i];
   j++;
   }
   if(min2>s[n-1-i])
   {
      min2=s[n-1-i];
  j++;
   }
   else if(max2    {
   max2=s[n-1-i];
   j++;
   }
}
min = (min1>=min2?min2:min1);
max = (max1<=max2?max2:max1);
printf("max:%d,min:%d\n",min,max);
printf("count:%d\n",j);
}

#12

#include "stdio.h"
int main()
{
int s[16]= {123,324,235,3124,345,2134,43,123,512,12,12,34,12,445,14325,-12};
int n=sizeof(s)/4;
printf("%d\n",n);
int min1,min2,max1,max2;
min1 = s[0];
max1 = s[0];
min2 = s[n-1];
max2 = s[n-1];
int maxcount;
int min,max;
maxcount = (n%2==0?n/2:n/2+1);
int i,j=0;
for(i=1;i {
   if(min1>s[i])
   {
      min1=s[i];
  j++;
   }
   else if(max1    {
   max1=s[i];
   j+=2;
   }
   if(min2>s[n-1-i])
   {
      min2=s[n-1-i];
  j++;
   }
   else if(max2    {
   max2=s[n-1-i];
   j+=2;
   }
}
min = (min1>=min2?min2:min1);
max = (max1<=max2?max2:max1);
printf("max:%d,min:%d\n",max,min);
printf("count:%d\n",j);
}

#13

设两个单元分别保存当前最大，最小值，然后依次和数组中各元素比较，如果比当前最大还要大，那自然不用再跟当前最小的那各比较，对求最小值也同理，介于当前最大，最小值之间则要比较两次，不过总共比较次数肯定小于2(n-1)=2n-2次

#include "stdio.h"
int main()
{
int s[16]= {123,324,235,3124,345,2134,43,123,512,12,12,34,12,445,14325,-12};
int n=sizeof(s)/4;
printf("%d\n",n);
int min1,min2,max1,max2;
min1 = s[0];
max1 = s[0];
min2 = s[n-1];
max2 = s[n-1];
int maxcount;
int min,max;
maxcount = (n%2==0?n/2:n/2+1);
int i,j=0;
for(i=1;i {
   if(min1>s[i])
   {
      min1=s[i];
   }
   j++;
   if(max1    {
   max1=s[i];
   }
   j++;
   if(min2>s[n-1-i])
   {
      min2=s[n-1-i];
   }
    j++;
   if(max2    {
   max2=s[n-1-i];
   }
j++;
}
min = (min1>=min2?min2:min1);
max = (max1<=max2?max2:max1);
printf("max:%d,min:%d\n",max,min);
printf("count:%d\n",j);
}

#14

1.
int s[n];
int min(0), max(1);

if(s[min]>s[max])     // 1 次
{
   min=1; max=0;
}
for(int i=2; i {
   if(s[i]>s[max]) max=i;
   else
   if(s[i] }
输出min, max

总次数不超过 1+2(n-2)   = 2n-3 < 2n-2
平均次数为   1+1.5*(n-2)= 1.5n-2
注:没有加上对n值是否>1的判断

2.
求最大值和最小值的算法比较次数证明:
1.求一个数组的最大值,比较次数为n-1
2.从剩下的元素中找最小值,比较次数为n-2,
  这个值(n-2)不能够再小,
  这是因为,我们不能够对前面求得最大值的结果加以利用,
  所有剩下的值都不超过最大值
故算法比较次数为(n-1)+(n-2)=2n-3

3.特殊情况下,比较次数可以达到n-1,
  这种情况就是这个数组本身就有序(从大到小、或相反)

#15

典型的分而治之的算法

#16

n个元素的数组，单一的找最大或者最小，都需要n－1次比较
如果独立找两次，总需要比较量就是2n-2次

如果只是达到比这个数目小的目的，很简单，只要那里节约下一次比较就可以了
假定，比较到某个数据的时候，当前的最大和最小数据是max和min
把当前数据和min比较，如果它比min小，自然就不要和max比较了
如果它比max大自然也不用和min比较了
而这样的数肯定是存在的，因此小于2n－2的算法没有什么讨论价值

以前在算法和数据结构当中讨论过小于3/2 ×N －2的算法
原理如下
abcd四个数比较的时候，两两分组，找出各自的大的和小的，需要2次比较
然后大的和大的比较，找到最大，小的和小的比较找到最小
一共是4次比较，找到了最大和最小

对于N个数据的时候，把他们分成N/4个组，每组用4次比较找到其中的最大和最小
总共用了N次比较

把N/4个组内最大的数据之间进行比较找到最大的，需要N/4-1次比较
在N/4个组内最小的数据之间进行比较找到最小的，也需要N/4-1次比较

这样，找到了N个数据当中最大和最小的数据，需要的总比较次数就是
N ＋ N/4 -1 + N/4 - 1 = 3 / 2 * N - 2次

#17

#include "stdafx.h"

#include "stdio.h"
int main()
{
int s[15]= {123,324,235,123123123,345,2134,43,123,12312323,12,12,34,12,14325,-12};
int n=sizeof(s)/4;
printf("%d\n",n);
int min1,min2,max1,max2;
min1 = s[0];
max1 = s[0];
min2 = s[n-1];
max2 = s[n-1];
int maxcount;
int min,max;
maxcount = n/2;//==0?n/2:n/2);
printf("%d\n",maxcount);
int i,j=0;
for(i=1;i {
   if(min1>s[i])
   {
      min1=s[i];
   }
   j++;
   if(max1    {
   max1=s[i];
   }
   j++;
}
maxcount=n-maxcount;
for(i=1;i {
   if(min2>s[n-1-i])
   {
      min2=s[n-1-i];
   }
    j++;
   if(max2    {
   max2=s[n-1-i];
   }
j++;
}
min = (min1>=min2?min2:min1);
max = (max1<=max2?max2:max1);
printf("max:%d,min:%d\n",max,min);
printf("count:%d\n",j);
}

#18

ringking007(四叶clover) ( ) 信誉：100  2005-03-04 15:50:00  得分: 0

   int min,max;
min=s[0];
max=s[0];
for(i=1;i      {
  if(min   if(max>s[i])max=s[i];
  }

#19

回复人： jialuo(jialuo) ( ) 信誉：100  2005-03-04 17:07:00  得分: 0

   UPCC(杂食动物):

如果是10个数,你的比较次数可能会达20次
if (n < 1) return false; 1次
if (n == 1)         1次
for (int i = s; i < n; i += 2)   5次     //这5次应该算吗？？？？？？？
if (w[i] > w[i+1])               5次
if (w[i] > w[Max]) Max = i;      5次
if (w[i+1] < w[Min]) Min = i + 1;  5次
这样的话你就有22次比较了  （是不是22 - 5 = 17次？？？）

#20

分治法求一个数组中最大元素的位置
查找数组中第i小的元素

推荐阅读

string
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
main
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
string
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
main
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
main
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
string
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
string
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
tree
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
string
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
string
Android开发笔记：使用Picasso加载网络图片等比例缩放

在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ... [详细]

蜡笔小新 2023-12-14 17:34:00
java
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
ascii
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
main
输出1000内能被3整除且个位数为6的所有整数的程序填充

本文介绍了一个程序，可以输出1000内能被3整除且个位数为6的所有整数。程序使用了循环和条件判断语句来筛选符合条件的整数，并将其输出。 ... [详细]

蜡笔小新 2023-12-13 16:30:11
byte
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11

独行小刀

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章