精华内容
下载资源
问答
  • 最快求最小值次小值

    千次阅读 2019-10-22 22:02:02
    本题目要求读入n个整数,要求用最少的比较次数,输出它们的最小值次小值。例如,对于12 13 1 10 34 1这6个数,最小值为1,次小值 为10。 输入格式: 输入有两行。第一行为整数个数n(≤1 000 000),第二行给出n...

    对代码的疑问:如果输入的某个数大于1000000怎么办?

    代码中有详细解释!但代码只适用于非负整数,有局限性。

    本题目要求读入n个整数,要求用最少的比较次数,输出它们的最小值和次小值。例如,对于12 13 1 10 34 1这6个数,最小值为1,次小值

    为10。

    输入格式:

    输入有两行。第一行为整数个数n(≤1 000 000),第二行给出n个以空格分隔的整数。

    输出格式:

    对每一组输入,在一行中输出最小值和次小值,中间以一个空格分隔,但行尾没有多余空格。如果输入数据不足两个,则输出“Invalid Input”。如果没有次小值,则输出“There is no second smallest element”。

    输入样例:

    6
    12 13 1 10 34 1 
    

    输出样例:

    1 10 
    

    思路:

    Java的题能用输入输出流就尽量别用Scanner!

    由于输入的数量n<=1000000,无论输入数据还是将输入的数据排序或比较,都有超时的陷阱,所以直接申请一个大数组,将输入的数据按照值对应的坐标放入数组中,这样就避免了排序或,直接从前往后寻找最大值和次小值就行了!

     

    //输入输出能用输入输出就尽量不用Scanner
    //类是动态加载的,eg:import java.io.*;不会影响效率,你的程序需要哪个类就会加载哪个类,但会加大class文件的大小
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    //BufferedReader比Scanner效率高不少!!!!
    public class 最快求最小值和次小值{
    	public static void main(String[] args) throws NumberFormatException, IOException {
    		/*
    		 * System.in的类型是InputStream,它代表的是键盘接受的输入,就是说键盘是数据源;
    		 * System.in的类型可以归结为节点流、字节流、输入流;
    		 * 接下来是InputStreamReader这个对象是处理流,字符流,输入流;
    		 * */
    		
    		/*
    		   read方法
                       功能:读取单个字符。
                       返回:作为一个整数(其范围从 0 到 65535 (0x00-0xffff))读入的字符,如果已到达流末尾,则返回 -1
    
               readLine方法
                       功能:读取一个文本行。通过下列字符之一即可认为某行已终止:换行 ('\n')、回车 ('\r') 或回车后直接跟着换行。
                       返回:包含该行内容的字符串,不包含任何行终止符,如果已到达流末尾,则返回 null 
            */
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		//parseInt是解析数字字符串
    		int n = Integer.parseInt(br.readLine());
            if(n<2)
            	System.out.println("Invalid Input");
    		else {
    			String Str = br.readLine();//n<=1000000
    			String[] s = Str.split(" ");
    			int[] num = new int[1000000];//不用自动初始化为0,默认全是0
    			for(int i=0;i<n;i++){
    				//放在数组中等于从小到大排序
    				num[Integer.parseInt(s[i])]+=1;//如果输入的某个数大于1000000怎么办
    			}
    			int min1=-1,min2=-1,j=0;
    			for(int i=0;i<1000000;i++){
    				//6
    				//12 13 1 10 34 1 
                    if(num[i]!=0&&j==1){//次小值
    					min2 = i;
    					break;
    				}
    				if(num[i]!=0&&j==0){//最小值
    					min1 = i;j=1;
    				}
    			}
    			if(min2==-1){
    				System.out.println("There is no second smallest element");
    			}
    			else {
    				System.out.println(min1+" "+min2);
    			}
    		}
    	}
    }

     

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

    很开心,这是今天的第三篇文章啦!下午健身也感觉非常过瘾,托付宿舍妹子从日本代购的护肤品也到了。耳边漂浮着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哈哈~

    展开全文
  • 在LabVIEW中,创建好多维数组,程序可以找出数组中的最值
  • public class 题8_5_1寻找数组中最小值与最大 { public static void main(String[] args) { int[] a={7,2,9,0,14,20,2,16}; getMaxAndMin0(a); } public static void getMaxAndMin0(int[] a){ ...
    package java程序员面试笔试宝典;
    
    public class 题8_5_1寻找数组中最小值与最大值 {
    	public static void main(String[] args) {
    		int[] a={7,2,9,0,14,20,2,16};
    		getMaxAndMin0(a);
    	}
    	public static void getMaxAndMin0(int[] a){
    		int min=a[0];
    		int max=a[0];
    		for (int i = 0; i +1< a.length; i+=2) {
    			if(a[i]<a[i+1]){
    				if(a[i]<min){
    					min=a[i];
    				}
    				if(a[i+1]>max){
    					max=a[i+1];
    				}
    			}else{
    				if(a[i+1]<min){
    					min=a[i+1];
    				}
    				if(a[i]>max){
    					max=a[i];
    				}
    			}
    		}
    		System.out.println("max:  "+max);
    		System.out.println("min:  "+min);
    	}
    	public static void getMaxAndMin(int[] a){
    		int max=a[0];
    		int min=a[0];
    		for (int i = 0; i < a.length; i++) {
    			if(a[i]>max){
    				max=a[i];
    			}else if(a[i]<min){
    				min=a[i];
    			}
    			
    		}
    		System.out.println("max:  "+max);
    		System.out.println("min:  "+min);
    	}
    	
    }
    

     

    展开全文
  • 在向量中寻找局部最小值或最大的函数集,在向量中找到最接近某个的点,以及清除所有内容的函数。
  • #include<iostream> #include<time.h> #define dim 5 using namespace std; void swap(double a, double b,double c[dim],int index_0,int index_1) { double temp; temp = a;... b...
    #include<iostream>
    #include<time.h>
    #define dim 5
    using namespace std;
    
    void swap(double a, double b,double c[dim],int index_0,int index_1)
    {
    	double temp;
    	temp = a;
    	a = b;
    	b = temp;
    	b = c[index_0];
    	a = c[index_1];
    }
    void sort(double a[dim])
    {
    	int s1 = 0, s2 = 0, i;
    	int s3 = 0;
    	for (i = 0; i < dim; i++)
    	{
    		if (a[i] < a[s1])
    		{
    			s1 = i;
    		}
    	}
    	
    	for (i = 0, s2 = (s1 + 1) % dim; i < dim; i++)
    	{
    		if (a[i] < a[s2] && i != s1)
    		{
    			s2 = i;
    		}
    	}
    	s3 = (s2 + 1) % dim;
    	if (s3 == s1)
    		s3 = (s2 + 1) % dim + 1;
    	for (i = 0; i < dim; i++)
    	{
    		
    		if (a[i] < a[s3] && i != s1&&i != s2)
    		{
    			s3 = i;
    		}
    	}
    	cout << "first_index is " << s1 << endl;
    	cout << "second_index is " << s2 << endl;
    	cout << "third_index is " << s3 << endl;
    }
    
    
    int main()
    {
    	srand(time(0));
    	double a[dim];
    	for (int i = 0; i < dim; i++)
    	{
    		a[i] = rand() % (5) - 2;
    		cout << " a[i] is " << a[i] << endl;
    	}
    	sort(a);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 寻找最大最小值

    2019-01-08 03:10:50
    问题描述:给定一个有n个数的序列集,求最大最小值。  解题思路:首先想到的的做法是首先任意选两个作为最小值和最大。然后剩下的n-2个分别于这两个进行比较即可。这样总共要 比较2*(n-2)。有...
  • 问题:寻找数组中的最小值和最大。   一道很简单的题目,一般有下面4种解法: 1 遍历两,每次分别找出最小值和最大。 2 只遍历一,每次取出的元素先与已找到的最小值比较,再与已找到的最大比较。 ...
  • 寻找数组的最大最小值

    千次阅读 2012-11-20 21:55:17
    问题:寻找数组中的最小值和最大。   一道很简单的题目,一般有下面4种解法: 1 遍历两,每次分别找出最小值和最大。 2 只遍历一,每次取出的元素先与已找到的最小值比较,再与已找到的最大比较。 3...
  • 主要介绍了JavaScript数据结构与算法之二叉树实现查找最小值、最大、给定算法,涉及javascript二叉树定义、赋值、遍历、查找等相关操作技巧,需要的朋友可以参考下
  • C++寻找最大值最小值

    2020-05-18 14:33:18
    各类型变量寻找最大 代码 vector寻找最大 #include <algorithm> #include <iostream> int main() { std::vector<double> v {1.0, 2.0, 3.0, 4.0, 5.0, 1.0, 2.0, 3.0, 4.0, 5.0}; std::...
  • C++寻找数组最大最小值

    万次阅读 2018-08-13 13:52:42
    C++里面有好多自带函数可以直接用,比如寻找数组中的最大最小值其实是有函数的,如下 #include &lt;iostream&gt; using namespace std; #include &lt;algorithm&gt; int main() { int n; cin &...
  • 今天编就为大家分享一篇python寻找list中最大最小值并返回其所在位置的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随编过来看看吧
  • python 寻找最大最小值

    千次阅读 2019-03-26 16:00:05
    输入一串数字,返回最小值和最大 def getListByInput(nums): nums_list = [] for n in nums: if(n == ','): continue else : nums_list.append(n) return nums_list # ...
  • System.out.println("最小值:"+min); System.out.println("中间:"+middle); } public static int max(int x,int y,int z) { // int max=0; // max=x>y?x:y; // max=max>z?max:z; // return ...
  • 寻找数组中的最大最小值
  • 找出数据集合中的最小值和最大的两种算法比较...通常寻找最大值最小值的方法方法一:void max_min(int* array,int size,int* max){int tmp = 0;for(tmp = 0,*max = array[0];tmp < size;tmp++){*max = *max...
  • 设计一个最优算法来同时找到n元素数组中的最大最小值,要求使用最小的比较次数: 算法导论(3th Edition)9.1: https://blog.csdn.net/shuiziliu1025/article/details/50958190 1.5N即可 应用:选择排序...
  • 解法一: 扫描一次数组找出最大;...对大者组扫描一找出最大,对者组扫描一找出最小值。 代码(略) 比较1.5N-2,但需要改变数组结构 解法三: 每次比较相邻两个数,较大者与MAX比较,...
  • 寻找数组中的最小值与最大有很多方法:比如分别进行两遍历,一求最大,一最小值,需要比较2N,或者取单元素法,用两个变量分别表示最小值和最大,min表示最小值,max表示最大,遍历一数组,每次...
  • min是最小值,minlist是位置的数组 具体看代码,很清楚了 # count = 0 def find_mins(A,begin,end,min,minlist): if begin == end: if A[begin]< min: min = A[begin] minlist = [begin] elif A[begin]==min...
  • 问题:寻找数组中的最小值和最大
  • 今天主要聊聊,给定一个数组,如何同时求出最大最小值。常规的做法是遍历一遍,求出最大最小值。 求数组的最大最小值 #include <stdio.h> void max_and_min(int *arr, int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 68,059
精华内容 27,223
关键字:

寻找最小值次小值