精华内容
下载资源
问答
  • 找出数组中最大值和次大

    千次阅读 2015-07-18 14:12:15
    如何找出一个数组中的最大值和次大值,并且找出它们的位置。 思路: 假设只有四个数字,分成两组,前两个比较一得出最大和次大,后两个比较一得出最大和次大,则四个数字的最大值就是两个较大值中最大值。而...

    题目:

    如何找出一个数组中的最大值和次大值,并且找出它们的位置。

    思路:

    假设只有四个数字,分成两组,前两个比较一次得出最大和次大,后两个比较一次得出最大和次大,则四个数字的最大值就是两个较大值中的最大值。而次大值就是刚才那两个比较中的较小的和另外一组的次大值比较。举个例子:1 4 3 5 。较大值4 < 较大值5,则5是最大值,然后较大值4 和另一组的次大值3 比较,得出次大值为 4。

    对于n个数字的数组来说,可以使用分治递归的方法,得出左右两组中的最大值和次大值,然后利用上面的方法得出最大值和次大值。

    代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    void maxAndSec(vector<int> &nums , int left , int right , int &Max , int &secMax)
        {
            if(left == right)
            {
                Max = nums[left];            
    			secMax = INT_MIN;
                return;
            }
            if(left == right-1)
            {
                 secMax = min(nums[right] , nums[left]);
                 Max = max(nums[right] , nums[left]);
    			 return;
            }
            int mid = (left + right)/2;
            int leftMax = 0 , leftSec = 0 ;
            maxAndSec(nums, left , mid , leftMax , leftSec);
            int rightMax = 0 , rightSec = 0;
            maxAndSec(nums , mid+1 , right , rightMax , rightSec);
            Max = max(leftMax , rightMax);
    		if(leftMax < rightMax)
    			secMax = max(leftMax , rightSec);
    		else
    			secMax = max(rightMax , leftSec);
        }
    
    void maxAndSec2(int *nums , int len)
    {
    	if(len == 0)
    		return ;
    	int Max = nums[0];
    	int secMax = INT_MIN;
    	for(int i = 1 ; i < len ; i++)
    	{
    		if(nums[i] > Max)
    		{
    			secMax = Max;
    			Max = nums[i];
    		}
    		else
    		{
    			if(nums[i] > secMax)
    			{
    				secMax = nums[i];
    			}
    		}
    	}
    	cout<<Max<<endl<<secMax<<endl;
    }
    int main()
    {
    	int num[7] = {2,4,3,5,6,7,3};
    	maxAndSec2(num , 6);
    	vector<int> nums(num , num+7);
    	int max = 0 , secmax = 0 ;
    	maxAndSec(nums,0,6,max,secmax);
    	cout<<"最大值是:"<<max<<endl<<"次大值是:"<<secmax<<endl;
    }
    	
    






    展开全文
  • 数组中的最大值和次大值 输入:A[1…n]=<a1, a2, …, an> 输出:max1,max2 【注:max1表示最大值,max2表示次大值】 2. 代码 for (int i = 1; i <= n; i++) { if (A[i] > max1) { max2 = max1; ...

    1. 问题

    数组中的最大值和次大值

    输入:A[1…n]=<a1, a2, …, an>
    输出:max1,max2

    【注:max1表示最大值,max2表示次大值】

    2. 代码

    // max1 和 max2首先均被初始化为int范围内最小值,
    // 并且保证数组A[1..n]中的任何一个值比int范围内最小值都大。
    for (int i = 1; i <= n; i++) {
    	if (A[i] > max1) {
    		max2 = max1;
    		max1 = A[i];
    	} else if (A[i] > max2) {
    		max2 = A[i];
    	}
    }
    

    3. 算法正确性证明

    算法证明所用技术:循环不变式

    证明要点:
    初始化: 首先证明在第3次循环之前,循环不变式成立。即,对于数组中前2 (31=2)(3 - 1 = 2)个数,max1中存储最大值,max2存储次大值。
    保持: 证明从第3次循环往后,每次迭代保持循环不变式。即,如果第k次执行之前,循环不变式(对于数组前 k1k-1 个数,max1中存储最大值,max2存储次大值)成立,第k+1次执行之前,循环不变式(对于数组前 k+11k+1-1 个数,max1中存储最大值,max2存储次大值,)仍然成立。
    终止: 最后研究在循环终止时发生了什么。导致循环终止的条件是i <= n。我们有:对于数组中的前n个数,max1存储最大值,max2存储次大值。

    我们在这里仅证明保持部分。
    第k次执行循环体之前: 对于数组前k-1个数,max1存储最大值,max2存储次大值。
    第k次执行循环体: 分支1,若A[k]>max1,则执行max2 = max1; max1 = A[k]。 由于max1存储的是前k-1个数的最大值,因此,前k个数的次大值就是max1,所以将max1的值转存至max2。而将A[k]存入max2,这样,max1存储的就是前k个数的最大值了分支2,若max1>A[k]>max2,则执行max2 = A[k]。由于max1比A[k]大,所以,前k个数的最大值依然是max1,所以max1的值不变。但A[k]比max2大,并且又因为max2存储的是前k-1个数的次大值,因此比当前max2大的数只有max1和A[k],又因为max1大于A[k],所以,A[k]是前k个数的次大值。故需要将A[k]的值转存至max2。
    第k+1次执行循环体之前: 对于数组前k个数,max1存储最大值,max2存储次大值。

    展开全文
  • #include&lt;stdio.h&gt; //改数组大小只需要修改 N后面的数字 #define N 5 int main(void) ... //定义最大值并赋值 int mid= 0; //定义次大值并赋值 for(int i = 0;i&lt;N;i...
    
     
        #include<stdio.h>
        //改数组大小只需要修改 N后面的数字
        #define N 5
    
    
    	int main(void)
        {
    
    	int arr[N]={5,6,8,3,9};
    		
    	int max= 0;  //定义最大值并赋值
    	int mid= 0;  //定义次大值并赋值
    	for(int i = 0;i<N;i++){
    	    /*因为arr[i]是固定的 ,所以可以用arr[i]先和max比较,如果大于max 则
    		把max的值赋给mid的值,然后把arr[i]赋给max  这样max肯定比mid大*/	
    	    if(arr[i]>max)
            {
    	        mid = max;
    	        max =arr[i];
    	    }else if(arr[i]>mid)
            {
                /*  另一种情况 arr[i]处于两者之间*/
    	    	mid = arr[i];//  则吧arr[i]赋给mid
    	    }
    	}
    	printf("max=%d,mid=%d\n",max,mid);
    	return 0;
    	}
    

     

     

     

    展开全文
  • 很开心,这是今天的第三篇文章啦!下午健身也感觉非常过瘾,...第三篇是关于寻找数组中最大值和最小值。第一看到这个题目的时候,楼主稍微鄙视了一下,因为觉得这个题目有什么好做的。但是楼主还是看了看《编程之

    很开心,这是今天的第三篇文章啦!下午健身也感觉非常过瘾,托付宿舍妹子从日本代购的护肤品也到了。耳边漂浮着Hebe田馥甄的《魔鬼中的天使》文艺的声线,一切都好棒,O(∩_∩)O哈哈~。爱生活,爱音乐,爱运动,额,当然还有要爱学习啦!加油↖(^ω^)↗

    额,扯远了。第三篇是关于寻找数组中的最大值和最小值。第一次看到这个题目的时候,楼主稍微鄙视了一下,因为觉得这个题目有什么好做的。但是楼主还是看了看《编程之美》上的写的,发现还是有必要记录一下,不一样的思考方式。很赞!大家和楼主一起哦,Are you ready?呼呼(~ o ~)~zZ

    题目一:寻找数组中的最大值和最小值

    解法一

    把寻找数组中的最大值和最小值看成是两个独立的问题,对于每个独立的问题的话,我们可以采用一次循环遍历的方法得到。假设数组的长度为N,那么总共需要比较的次数为2N。解法过于简单,代码略过啦。

    解法二

    假设数组为[5, 6, 8, 3, 7, 9],

    • 每相邻的两个元素比较,较大者放在偶数位,较小者放在奇数位。完成这一步骤后,偶数位为6, 8, 9。奇数位为5, 3, 7。

    • 然后遍历偶数位可以获得数组的最大值,遍历奇数位可以获得数组的最小值。

    • 比较次数:0.5N+0.5N+0.5N=1.5N看代码:
    #include <iostream>  
    #include<limits>
    
    using namespace std;  
    
    void partion(int *pArray, int len);
    
    int main()  
    {  
        int a[] = {1, 2, 3, 4, 5, 6, 0, 7};
        int len = sizeof(a) / sizeof(int);
        partion(a, len);
        int MAX = a[0];
        int MIN = a[1];
    
        int i = 0;
        int j = 1;
    
        for (; i < len - 1, j < len; i = i + 2, j = j + 2)
        {
            if (a[i] > MAX)
            {
                MAX = a[i];
            }
            if (a[j] < MIN)
            {
                MIN = a[j];
            }
        }
    
        //说明有一个数单出来
        if (i == len - 1)
        {
            if (a[i] > MAX)
            {
                MAX = a[i];
            }
            if (a[i] < MIN)
            {
                MIN = a[i];
            }
        }
    
        cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
        system("pause");
    }  
    
    //将数组分成两个子数组,较大值放在偶数位,较小值放在奇数位
    void partion(int *pArray, int len)
    {
        int i = 0;
        while (i < len - 1)
        {
            //如果奇数位的比偶数位的大,则交换位置
            if ((pArray[i + 1] > pArray[i]))
            {
                swap(pArray[i + 1], pArray[i]);
            }
            i += 2;
        }
    }

    解法三

    解法二虽然降低了比较的次数,可是却破坏了数组的顺序。绝大多数时候,我们只是想获取数组中的最大值和最小值,并没有想要改变数组的顺序,所以解法二,会有问题。那这就是解法三改进的点了,同样和解法二一样,每相邻的两个元素进行比较,但是不改变数组的顺序。而是选择用两个变量,如MAX和MIN来记录最大值和最小值并看情况更新。看下图所示
    这里写图片描述
    看代码:

    #include <iostream>  
    #include<limits>
    
    using namespace std;  
    
    void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);
    
    int main()  
    {  
        int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 1, 13, 67, 89, 0,100, -1};
        int len = sizeof(a) / sizeof(int);
        int MIN = numeric_limits<int>::max();;
        int MAX = 0;
        int tempMin = 0;
        int tempMax = 0;
        int i = 0;
        while (i < len - 1)
        {
            if ((a[i] >= a[i + 1]))
            {
                tempMax = a[i];
                tempMin = a[i + 1];
            }
            else
            {
                tempMax = a[i + 1];
                tempMin = a[i];
            }
            if (tempMax > MAX)
            {
                MAX = tempMax;
            }
            if (tempMin < MIN)
            {
                MIN = tempMin;
            }
            i += 2;
        }
        if (i == len - 1)
        {
            if (a[i] < MIN)
            {
                MIN = a[i];
            }
            if (a[i] > MAX)
            {
                MAX = a[i];
            }
        }
    
        cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
        system("pause");
    }  

    解法四

    分治法,把N个元素的最大值和最小值问题,分别求出N/2维左半部分和右半部分的最大值和最小值。左半部分最大值和右半部分最大值比较,较大值为最后的最大值;同样,左半部分的最小值和右半部分的最小值比较,较小者为最后的最小值。看代码:

    #include <iostream>  
    
    using namespace std;  
    
    void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);
    
    int main()  
    {  
        int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 1, 13, 67};
        int len = sizeof(a) / sizeof(int);
        int MIN = 0;
        int MAX = 0;
        searchMinAndMax(a, 0, len-1, &MIN, &MAX);
        cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
        system("pause");
    }  
    
    void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX)
    {
        int middle = (low + high) / 2;
    
        //如果分组只剩下两个数字或者一个数字,则直接比较
        if (high - low <= 1)
        {
            if (pArray[low] > pArray[high])
            {
                *MIN = pArray[high];
                *MAX = pArray[low];
                return;
            }
            else
            {
                *MIN = pArray[low];
                *MAX = pArray[high];
                return;
            }
        }
    
        int lMin = 0;
        int lMax = 0;
        int rMin = 0;
        int rMax = 0;
    
        searchMinAndMax(pArray, low, middle, &lMin, &lMax);
        searchMinAndMax(pArray, middle + 1, high, &rMin, &rMax);
    
        *MIN = min(lMin, rMin);
        *MAX = max(lMax, rMax);
    }

    需要比较的次数为1.5N2

    题目二:寻找数组中的最大值和次大值

    这道题是《编程之美》上题目一的扩展问题,为了巩固前面的知识,楼主决定把这道题也给做了,运用分治思想。主要思想和题目一类似。直接看代码:

    #include <iostream>  
    
    using namespace std;  
    
    void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);
    
    int main()  
    {  
        int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 67};
        int len = sizeof(a) / sizeof(int);
        int MAX = 0;
        int SECONDE_MAX = 0;
        searchMinAndMax(a, 0, len-1, &SECONDE_MAX, &MAX);
        cout << "最大值为" << MAX << " 次大值为" << SECONDE_MAX << endl;
        system("pause");
    }  
    
    void searchMinAndMax(int *pArray, int low, int high, int *SECONDE_MAX, int *MAX)
    {
        int middle = (low + high) / 2;
    
        //如果分组只剩下两个数字或者一个数字,则直接比较
        if (high - low <= 1)
        {
            if (pArray[low] > pArray[high])
            {
                *SECONDE_MAX = pArray[high];
                *MAX = pArray[low];
                return;
            }
            else
            {
                *SECONDE_MAX = pArray[low];
                *MAX = pArray[high];
                return;
            }
        }
    
        int lSeMax = 0;
        int lMax = 0;
        int rSeMax = 0;
        int rMax = 0;
    
        searchMinAndMax(pArray, low, middle, &lSeMax, &lMax);
        searchMinAndMax(pArray, middle + 1, high, &rSeMax, &rMax);
    
        *SECONDE_MAX = max(lSeMax, rSeMax);
        *MAX = max(lMax, rMax);
    }

    比较次数也是1.5N2

    楼楼这篇文章就到此为止啦,还剩下三篇就可以开专栏了哦。加油加油!!!希望大家一天都充满活力,O(∩_∩)O哈哈~

    展开全文
  • /** ... * @Description 给定一个数组输出这个数组中最大值和最小值 */ public class BigAndSmall4 { public static void main(String[] args) { int a[] = {6,34,23,41,87,3,7}; minMa...
  • java数组中输出最大值

    2020-07-06 18:42:47
    定义一个int类型的数组找出数组中最大值 代码: public static void main(String[] args) { // 定义一个int类型的数组找出数组中最大值 int[] a= {-1,-8,-2,-5,-3}; int max=a[0]; for(int i=0;i<a....
  • 本文主要用于将一个数组中最大值、最小值和次大值通过java代码实现出来。有的伙伴肯定也想过可以将数组进行排序在直接取值,虽然这样也可以,但终究代码效率会慢一些。如果需要具体详情,可以参考数据结构关于...
  • 出数组最大值和次大

    千次阅读 2015-03-30 18:05:14
    2.遍历数组,比较当前的最大值角标的元素遍历得到数组元素的大小;如果数组元素大于当前最大值,更新最大值角标为遍历到的数组元素角标,直到遍历完成程序设计语言描述:int getMax(int[] arr){ int max = 0;
  • //由于上面的比较若max比后面的,若有小于max但是 //大于sec_max的的话将不会执行,于是添加以下判断 if ( *sec_max [i] && arr[i] ) { *sec_max = arr[i]; } } if (max == *sec_max ) { ...
  • * 功能描述:查找数组中最大值,最小值,第二值 * 编辑人:王廷云 * 编辑日期:2017-12-12 */ #include &amp;lt;stdio.h&amp;gt; #define NR 10 // 数组元素个数 /*主函数开始*/ int ...
  • java一维数组中找最大值和最小值

    千次阅读 2019-08-17 00:26:06
    /** * @author 大杨 *@date 2019年8月13日 上午11:07:10 */ public class LinearArray { ...//定义一维数组,并初始化,找到数组中最大值和最小值 int[]array=new int[10]; for(int i=0;i<array.length...
  • 一维数组找出其中最大的数第二的数。 #include<stdio.h> void main() { int a[]={1,23,45,6,34,2,67,345,67}; int len = sizeof(a)/sizeof(a[0]); int i,max1=0,max2=0; for(i=0;i<len;i++) { ...
  • 给定一个数组输出数组中最大值和最小值 //传入需要验证的数组,在main里面调用该方法 public static void demo05(int[] arrays) { int max = arrays[0], min = arrays[0]; for (int i = 0; i < arrays....
  • 定义一个数组输出数组中最大值和最小值 public class TestArray1 { public static void main(String[] args) { int[] a = new int[] {1, 2, 655, 34, 98, 66};//定义数组 int max = a[0];//默认第一个数,...
  • 用分治法,把数组分成2组,2组内分别用两两比较淘汰的方法找出各自的最大值(一共n-1比较), 最后出来的2个最大值比较,较的那个是最大值,第二的值在较小的那个所有跟最大值比较过的元素(一共log_2 n -1...
  • 给定一个数组输出数组中最大值和最小值。 public class TestMaxMin { public static void main(String[] args) { int[] nums={2,4,6,12,35,77,7,1}; int a=0; //标记下标 //min Min(nums,a); Max(nums,a)...
  • 定义两个数组两个数组中找出最大值; import java.util.Arrays; public class For { public static void main(String[] args) { int[] arr= {999,12,13,1,88,4,99}; int[] arr1= {3,67,56,567,888,4,9}...
  • 【Java】从数组中寻找最大值

    千次阅读 2019-05-24 21:04:43
    Java代码:从数组中寻找最大值c语言思想相同),在一个方法里先设一个最大值max=0,循环数组让max依次和数组array[i]进行比较,如果array[i]>max,将数组织赋给max,将会实现数组中最大值是max.注意Java设...
  •  if(a[i]>a[index_max]) //用i跑数组,a[i]比最大值大,则a[index_max]是当前次大值,a[i]是最大值,下标交换时注意顺序  {  index_sec=index_max;  index_max=i;  }  else  if(a[i]>a[index_sec]) //若a[i...
  • 在一个方法实现一个数组中找到该数组最大值和次大值并返回。 import java.util.Scanner; public class four { void getTwo(int[] a) { for (int i = 0; i < a.length; i++) { int max = i; for ...
  • 使用Python numpy 找数组中最大值次大值、第三值… 下面就贴上代码 def find_max(a): b = np.zeros(4) c = np.zeros(4) c[0] = np.max(a) #最大值 b[0] = np.where(a==c[0])[0] #最大``值位置 new_a = np....
  • PTA-求二维数组中最大值和最小值

    万次阅读 2019-05-20 17:01:56
    求二维数组中的最大值和最小值 编写程序,输入一个3×3的二维整数数组,输出其中最大值、最小值。 输入格式: 输入9个整型数到二维数组a[3][3],数据之间用一个空格分隔。 输出格式: 输出数组a的最大值和最小值 ...
  • 数组——求数组中最大值

    千次阅读 2019-09-05 10:18:02
    2.默认最大值是这个数组中的第一个元素 3.然后用for循环遍历,让数组中的每一个元素与max进行比较,如果其元素比max的值,就将其值赋给max,否则,进行下一轮的比较 4.最后输出这个max var arr = [1, 20, 30, ...
  • 1、循环对比 findMaxValue(arr) { let max = 0; // 最大值 for (let i=0; i<arr.length;... max) { // 当前值大于最大值,赋值为最大值 max = arr[i]; } } return max; } 2、Arrays.sort() 实现 f
  • //求一维数组中最大值 function max(){ $array=array(157,3,415,66,9,4,52,14); //假设一个最大值,来自于本数组 $max=$array[0]; //循环比较 两两相比的留下 for($i=0;$i<...
  • js找出数组中最大值

    千次阅读 2019-08-28 10:03:57
    首先对数组进行排序(从大到小),第一项为最大值 arr.sort((num1, num2) => { return num1 - num2 }) arr[0] 5.数组reduce arr.reduce((num1, num2) => { return num1 > num2 ? num1 : num2} ) ...
  • 本文意在求某二维数组中, 最大值, 且最大值所在行数列数. 理一理思路: 首先, 根据题意,我们要明白二维数组元素的排列方式, 表达形式, 为了方便介绍,我们先将所有的元素都进行赋值; 创建一个完整的二维数组;(赋...
  • 1. 两循环查找 ...//找到最大的元素和次大的元素 void find(int a[],int b[]) { int max1=a[0]; int max2=-1000,t; for(int i=0;i<6;i++) { if(a[i]>max1) { max2=max1; max1=a[i]; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 484,544
精华内容 193,817
关键字:

从数组中找出最大值和次大值