同时找到最大值和最小值——编程之美

绝地灬酷狼 2022-08-06 15:06 196阅读 0赞

**同时找到最大值和最小值——编程之美**

给定一个数组，我们可以同时找到其中的最大数和最小数吗？要求时间复杂度尽可能的小。

编程之美上面提供了三个思路，我把它们都实现了，并做一些讲解补充。

**思路一：**

两次遍历，分别得到最大值和最小值。时间复杂度为O(2\*N)。

**思路二：**

把最前面的两个数作为最值的候选，然后后面的数两两一组，分别让其中的较大值和候选最值比较，让其中的较小值和候选最值比较。

感觉这种方法和推排序有点儿类似。。

**思路三：**

采用分治法思想，把整个数组一分为二，让左边的最值和右边的最值分别比较，这里有个递归的过程，主要跳出递归的条件是当数组的begin和end相差小于等于1的时候，跳出。

上面三个思路的代码如下：

#include<iostream>
    using namespace std; 
    
    struct Pair
    {
    	int max, min; 
    };
    
    // 遍历两次，时间复杂度为O(2*N)
    Pair minMax_1(int a[], int n)
    {
    	int max = a[0], min = a[0]; 
    
    	for(int i = 0; i < n; i++)
    	{
    		min = a[i] < min ? a[i]:min; 
    		max = a[i] > max ? a[i]:max; 
    	}
    
    	Pair p; 
    	p.max = max; 
    	p.min = min; 
    
    	return p; 
    }
    
    // 两两比较，时间复杂度是O(1.5*N)
    Pair minMax_2(int a[], int n)
    {
    	int max = a[0], min = a[1]; 
    	if(max < min)
    		swap(max, min); 
    
    	for(int i = 2; i < n; i = i + 2)  // 递进2个
    	{
    		int tmpMin = a[i]; 
    		int tmpMax = a[i+1]; 
    		if(tmpMax < tmpMin)
    			swap(tmpMin, tmpMax);   // 候选
    
    		max = max > tmpMax ? max:tmpMax; 
    		min = min < tmpMin ? min:tmpMin; 
    	}
    
    	// 防止长度为奇数
    	max = max > a[n-1] ? max:a[n-1]; 
    	min = min < a[n-1] ? min:a[n-1]; 	
    
    	Pair p; 
    	p.max = max; 
    	p.min = min; 
    
    	return p; 
    }
    
    // 分治法，时间复杂度也是O(1.5*N)
    Pair minMax_3(int a[], int begin, int end)
    {
    	Pair P; 
    	if(end - begin <= 1)
    	{
    		P.max = a[begin] > a[end] ? a[begin]:a[end]; 
    		P.min = a[begin] < a[end] ? a[begin]:a[end]; 
    		return P; 
    	}
    
    	Pair PL = minMax_3(a, begin, begin + (end - begin) / 2); 
    	Pair PR = minMax_3(a, begin + (end - begin) / 2 + 1, end); 
    	P.max = PL.max > PR.max ? PL.max:PR.max; 
    	P.min = PL.min < PR.min ? PL.min:PR.min; 
    
    	return P; 
    }
    
    int main()
    {
    	Pair P; 
    	int a[] = {3, 6, 1, 8, 0}; 
    	int n = 5; 
    
    	// solution 1 
    	P = minMax_1(a, n); 
    	cout<<P.min<<' '<<P.max<<endl; 
    
    	//solution 2
    	P = minMax_2(a, n); 
    	cout<<P.min<<' '<<P.max<<endl; 
    
    	//solution 3
    	P = minMax_3(a, 0, n-1); 
    	cout<<P.min<<' '<<P.max<<endl; 
    
    	return 0; 
    }