C++程序 查找正方形矩阵中的最大值和最小值

C++程序 查找正方形矩阵中的最大值和最小值

给定一阶为n的正方形矩阵,在该矩阵中查找最大值和最小值。

示例:

输入: arr[][] = {5, 4, 9,
2, 0, 6,
3, 1, 8};
输出: 最大值 = 9,最小值 = 0

输入: arr[][] = {-5, 3,
2, 4};
输出: 最大值 = 4,最小值 = -5

朴素法:

我们使用线性搜索分别查找矩阵的最大值和最小值。查找最小值需要n 2 次比较,查找最大值需要n 2 次比较。总比较次数等于2n 2 。

// 查找矩阵中的最大值和最小值。
#include<bits/stdc++.h>
using namespace std;
  
void maxMin(int arr[3][3], int n)
{
    int min = INT_MAX;
    int max = INT_MIN;
     
    // 查找给定数组中的最大元素
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(max < arr[i][j]) max = arr[i][j];
        }
    }
     
    // 查找给定数组中的最小元素
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(min > arr[i][j]) min = arr[i][j];
        }
    }
    cout << "最大值 = " << max << ",最小值 = " << min;
}
  
int main(){
    int arr[3][3] = {{5, 9, 11} , {25, 0, 14} , {21, 6, 4}};
    maxMin(arr, 3);
    return 0;
}
// 该代码由KIRTI AGARWAL(KIRTIAGARWAL23121999)贡献。```  

输出

最大值 = 25,最小值 = 0

成对比较(高效方法):

从矩阵中选择两个元素,一个是矩阵行的开头,另一个是同一行的末尾,比较它们,然后将它们中较小的比较矩阵中的最小值,大的比较矩阵中的最大值。我们可以看到对于两个元素,我们需要3次比较,因此对于遍历整个矩阵,我们需要总共3/2 n 2 次比较。

注意:

这是数组的最大最小值的第3种方法的扩展形式。

// 查找矩阵中的最大值和最小值。
#include<bits/stdc++.h>
using namespace std;
 
#define MAX 100
 
void maxMin(int arr[][MAX], int n)
{
    int min = INT_MAX;
    int max = INT_MIN;
 
    // 逐行遍历数组
    for (int i = 0; i <n; i++)
    {
        for (int j = 0; j <= n/2; j++)
        {
            // 比较当前行开头和结尾的元素
            if (arr[i][j] > arr[i][n-j-1])
            {
                if (min > arr[i][n-j-1])
                    min = arr[i][n-j-1];
                if (max< arr[i][j])
                    max = arr[i][j];
            }
            else
            {
                if (min > arr[i][j])
                    min = arr[i][j];
                if (max< arr[i][n-j-1])
                    max = arr[i][n-j-1];
            }
        }
    }
    cout << "最大值 = " << max;
         << ",最小值 = " << min;
}
 
int main()
{
    int arr[MAX][MAX] = {5, 9, 11,
                        25, 0, 14,
                        21, 6, 4};
    maxMin(arr, 3);
    return 0;
}  

输出:

最大值 = 25,最小值 = 0

时间复杂度:O(n^2)

辅助空间:O(1) 因为没有额外的空间被占用。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例